조합1 [백준 11051] 이항 계수 2 www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 이항계수를 구하는 문제이다. nCk = n!/k!(n-k)!이지만 n과 k가 1000까지 입력을 받기 때문에 저 식대로 계산하면 오버플로우가 발생한다. 그래서 파스칼의 삼각형을 사용하여 구해준다. 파스칼의 삼각형은 dp를 사용해서 구한다. nCk = dp[i][j] if j=0 or i=j then 1 else dp[i][j] = dp[i-1][j-1] + dp[i-1][j]로 식을 세울 수 있다. #include using namespace std; int dp[1001][100.. 2020. 12. 23. 이전 1 다음
