백준 - 이항 계수 1 (11051)

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 1...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, through: i, by: 1) {
        dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
    }
}

print(dp[N][K])

조합을 구하는 공식을 사용할 수도 있겠지만 점화식을 사용해서 문제를 풀어보았다.

조합을 구하기 위해 사용되는 점화식은 다음과 같다.

dp[n][k] = dp[n-1][k-1] + dp[n-1][k]

먼저 dp[n][k] 는 nCk (n개 중에서 k개를 고르는 경우)를 뜻한다.

n개 중에서 k개를 고르는 상황은 두 가지로 나뉜다.

1. 이전 n-1개 중에서 k-1개를 고른 경우 (현재 보고 있는 데이터를 고르는 경우)
2. 이전 n-1개 중에서 k개를 고르는 경우 (현재 보고 있는 데이터를 고르지 않는 경우 → 이전 데이터들 중에서 k개를 모두 골라야 한다.)

두 경우의 수를 모두 더하면 조합의 결과를 구할 수 있다.