백준 (224) 썸네일형 리스트형 백준 11051 - 이항 계수 2 icpc.me/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 이항 계수 $\binom{N}{K}$를 구하는 문제이다. $N \leq 1000$이므로 점화식 $bino(n, k) = bino(n - 1, k) + bino(n - 1, k - 1)$을 단순한 이용한 재귀를 통해서는 구할 수 없다. 메모이제이션을 통해 배열에 값을 저장하면 빠르게 계산을 할 수 있다. 전체 코드 더보기 #include #include using namespace std; int bino[1001][1001] {}; int solve(int n, int r); int main() { memse.. 백준 11050 - 이항 계수 1 icpc.me/11050 이항 계수 $\binom{N}{K}$를 구하는 문제이다. 주어진 입력의 크기가 작으므로 반복문을 통해 식 $\frac{N!}{K!(N - K)!}$을 구해주면 된다. 전체 코드 더보기 N, R = map(int, input().split()) bunza = 1 bunmo = 1 for i in range(N-R+1, N + 1): bunza *= i for k in range(1, R + 1): bunmo *= k print(int(bunza / bunmo)) [ICPC] 백준 4811 - 알약 icpc.me/4811 N이 주어질 때 서로 다른 문자열의 개수를 $D_N$이라고 한다면 $D_1 = 1, D_2 = 2, D_3 = 5, D_4 = 14$ 가 예제 TC에 주어지고 이는 카탈란 수임을 알 수 있다. N이 작으므로 카탈란 수의 점화식 $C_N = \Sigma_{i = 0}^{N - 1}C_iC_{N - 1 - i}$을 이용해 동적계획법을 수행한 후 각 쿼리에 알맞은 값을 출력하면 된다. 전체 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include using namespace std; using ll = long long; ll dp[31]; int main() { cin.tie(0); ios:.. 백준 17268 - 미팅의 저주 icpc.me/17268 1670번과 요구상황이 동일한 문제이다. 1670번의 풀이를 참고하도록 하자. 백준 1670 - 정상 회담 2 icpc.me/1670 8명이 완벽하게 악수하는 경우의 수까지 직접 구해보자. 각 항을 $D_n$으로 표현했을 때 $D_2 = 1, D_4 = 2, D_6 = 5, D_8 = 14$이고 이는 카탈란 수임을 알 수 있게 된다. 카탈란 수를 적절히 구해주도록 하자. 다만 주어지는 나머지 987654321이 소수가 아니므로 페르마의 소정리를 통해 이항 계수에서 분모를 구할 수 없으므로 이항 계수 5를 해결하는 데 사용된 구현을 통해 카탈란 수를 구해주면 AC를 받을 수 있다. 전체 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44.. 이전 1 ··· 31 32 33 34 35 36 37 ··· 45 다음
