백준 11051번 이항 계수 2

< 백준 11051번 이항 계수 2 - 마포 코딩박 >

사용한 알고리즘: DP


 순열조합의 nCk를 계산하는 문제였습니다. 단, n이 최대 10^3으로 꽤 크게 주어져서 DP를 활용하여 문제를 해결하였습니다.

문제풀이는 다음과 같습니다.

(1) (코드 7~8)
 dp[n][k] = nCk%10007 값으로 설정했습니다.

(2) (코드 16~25)
 nC0=1, nC1=n 임을 이용하여 dp[i][0]=1, dp[i][1]=i 의 초기 설정을 했습니다.
 nCk = n-1Ck + n-1Ck-1 임을 이용하여 dp[2][2] ~ dp[1000][1000] 까지 계산해주었습니다.