BOJ-11051 이항 계수 2 Swift

문제

자연수 N과 정수 K가 주어졌을 때 이항 계수 (K  N)를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤N≤ 1,000, 0 ≤ K ≤ N)

출력

(N K)를 10,007로 나눈 나머지를 출력한다.

내가 푼 풀이

- (N K)는 (a+b)^N의 k번째 항의 이항계수이다.

- N = 0이면 (a+b)^0 = 1

- N = 1이면 (a+b)^1 = a + b 이므로 이항계수는 1 1 이된다.

위 이항계수는 다음과 같이 성립한다.

dp[n][k] = dp[n-1][k-1] + dp[n-1][k]가 된다.

점화식을 토대로 코드로 구현하면 다음과 같다.

 

 

import Foundation
// dp생성
var inputs = readLine()!.split(separator: " ").map{ Int($0)! }
var dp = Array(repeating: Array(repeating: 0, count: inputs[0]+1), count: inputs[0]+1)

// k = 0 , k = n 인경우 1 저장
// k는 n보다 클 수 없다.
// 나머지 경우 점화식에따라 입력
for i in 0..<dp.count {
    for j in 0..<dp.count {
        if j > i {
            continue
        }
        if j == 0 || i == j {
            dp[i][j] = 1
        } else {
            dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % 10007
        }
    }
}
print(dp[inputs[0]][inputs[1]])