[Swift 코테] 백준 11051 이항 계수2

---

스위프트의 경우 pascal(n: n-1, k: k-1) + pascal(n: n-1, k: k)를 DP를 이용해서 풀면 시간초과의 문제가 생긴다.

-> 시간초과를 해결하기 위해서는 2차원 배열에 값들을 저장해서 c[n-1][k-1] + c[n-1][k]를 계산해서 문제를 풀 수 있다.

1. 먼저 이항계수의 성질은 nCk = n-1Ck-1 + n-1Ck

2. nC0 = 1, nCn = 1

을 사용해서 문제를 풀 수 있다.

 

위의 2가지를 사용한다면 풀 수 있는 문제이지만, 한 번에 풀지 못해 다른 블로그를 참고했을 때 이해 되지 않던 점을 정리해보았다.

1. 범위를 k가 n을 초과할 수 없는 이유

    - 이항계수 값을 저장할 배열은 [N+1][N+1]개의 사각형 형태의 이차원 배열로 저장했지만

      당연히 이항계수에서 k는 n을 초과할 수 없는 삼각형 형태이기 때문에 k는 n을 초과할 수 없다.

 

2. 코드에서 nCn(예) 4C4)는 고려하지 않는 이유

    - if n == 0 || k == 0 은 0C0, 1C0, 2C0, 3C0...을 의미하고, 이때 값은 1이다.

    - 4C4 = 3C3 + 3C4

       3C4는 배열에서 c[3][4]로 0의 값을 가지고 있기 때문에 무시할 수 있다.

       따라서 4C4 = 3C3 + 3C4(0) = 2C2 + 2C3(0) = 1C1 + 1C2(0) = 0C0(1) + 0C1(0) = 1

       = 1의 값을 갖는다.

    

    - 하지만 조건문에 k == n 의 조건을 걸어도 무방하다.

 

3.  배열에 % 10007의 값을 저장하는 이유

    - n의 값은 1000이하의 값을 가진다, 이때 수가 무수히 크기 때문에 %10007의 나머지 값을 저장하는 것

    - 나머지 값들끼리 더해서 나머지 값을 계산해도 원래의 합에 나머지 값을 계산한 것과 동일하기 때문에 상관없다.

 

---

//코드

import Foundation

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

//c(n, k) = c(n-1, k-1) + c(n-1, k)

for n in 0...N{
    for k in 0...n{
        if n == 0 || k == 0 || k == n {
            c[n][k] = 1
        }else{
            c[n][k] = (c[n - 1][k - 1] % 10007 + c[n - 1][k] % 10007) % 10007
        }
    }
}

print(c[N][K])