백준 - 이항 계수 2 (11051)

let MOD = 10007
let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let (N, K) = (input[0], input[1])
var dp = Array(repeating: Array(repeating: 0, count: N + 1), count: N + 1)

// dp 테이블 초기화
for i in 0...N {
    dp[i][0] = 1
    dp[i][1] = i
    dp[i][i] = 1
}

// dp 테이블 채우기
for i in stride(from: 2, through: N, by: 1) {
    for j in stride(from: 1, to: i, by: 1) {
        dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % MOD
    }
}

print(dp[N][K])

이항 계수 1 문제와 마찬가지로 점화식을 사용해서 조합을 구한다.

단, dp 테이블에 10007 로 나눈 결과를 저장해야 한다. 이때 이 나머지 연산은 모듈러 연산의 성질을 만족한다.