백준 1010번 다리 놓기

정답 : 

var array = Array(repeating: Array(repeating: 0, count: 31), count: 31)
var result : [Int] = []
for i in 0...30 {
    for j in 0...i {
        if i == j || j == 0 {
            array[i][j] = 1
        }
        else {
            array[i][j] = array[i-1][j-1] + array[i-1][j]
        }
    }
}

let n = Int(readLine()!)!

for _ in 0..<n {
    let input = readLine()!.split(separator: " ").map{Int($0)!}
    let k = input[0]
    let t = input[1]
    result.append(array[t][k])
}
result.forEach{print($0)}

TMI : DP로 풀었지만, 난 왜 이런 점화식이 나온건지 아직도 이해 불가.. 이게 왜 실버5..?

설명하고 싶지만, 작성자가 멍청해서 점화식 자체가 이해되지 않는다..

 

나중에 다시 보겠다...

 

알고보니, 내가 문제를 잘못 이해했다. 다리가 서로 겹치지 않는다는 조건이, x자 크로스가 되면 안된다라는 것인줄 알았다..

 

겹친다는 것은, 한 목적지에 여러 다리가 있으면 안된다는 것..