11051번: 이항 계수 2

이항 계수 - 위키백과, 우리 모두의 백과사전

이항계수의 점화식

C(n, k) = C(n - 1, k - 1) + C(n - 1, k) 

반복문으로 DP 구현하기

// 입력 받기
let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let N = input[0], K = input[1]

// 이항 계수를 구해서 저장해놓을 이차원 배열 선언
var cache = Array(repeating: Array(repeating: -1, count: N + 1), count: N + 1)

// 초기값 넣기
for i in 1...N {
    cache[i][0] = 1 // 각 행의 처음과
    cache[i][i] = 1 // 마지막은 1
}

// 점화식을 통해서 cache 채워 나가기
for i in 1...N { //👉 N이 1일 수도 있으니까 1행을 이미 구한 상태라도 1부터 순회해야 함! (안그러면 N == 1일 때 error!)
    for j in 0...N {
        if cache[i][j] < 0 { // 아직 값을 구하지 않은 이항계수라면?
            cache[i][j] = (cache[i - 1][j - 1] + cache[i - 1][j]) % 10007
            //⭐️ 미리 나누어서 저장하자 (Int 범위 주의) -> 나머지끼리 더해도 나머지는 같다!
        }
    }
}

print(cache[N][K])

초기 값 (1)을 미리 넣지 않고 아래처럼 반복문 안에서 넣을 수도 있습니다.

for i in 1...N {
    for j in 0...N {
        if j == 0 || j == i {
            cache[i][j] = 1
        } else if cache[i][j] < 0 {
            cache[i][j] = (cache[i - 1][j - 1] + cache[i - 1][j]) % 10007
        }
    }
}

재귀함수로 DP 구현하기

// 입력 받기
let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let N = input[0], K = input[1]

// 이항 계수를 구해서 저장해놓을 이차원 배열 선언
var cache = Array(repeating: Array(repeating: -1, count: N + 1), count: N + 1)

// 재귀함수로 cache 채우기
func f(_ n: Int, _ k: Int) -> Int {
    // 이미 답을 구한 경우 cache에 있는 값 리턴
    if cache[n][k] != -1 {
        return cache[n][k]
    }
    
    // 각행의 첫 수, 마지막 수는 1
    if k == 0 || n == k {
        cache[n][k] = 1
    // 아니라면 점화식 사용
    } else {
        cache[n][k] = (f(n - 1, k - 1) + f(n - 1, k)) % 10007
    }
    
    // 모든 cache를 채우고 나서 원하는 값 리턴
    return cache[n][k]
}

print(f(N, K))