1010번: 다리 놓기

문제 풀이 아이디어

다리는 겹치면 안된다는 특성이 있기 때문에 서쪽에 N에 M개의 사이트가 있을 때

1. 일단 동쪽에 N개의 사이트를 정하면
2. N개의 각각 동쪽 사이트에 연결할 서쪽 사이트는 무조건 정해져있습니다. (서쪽 1번 사이트부터 동쪽의 1번 사이트와 연결)

따라서 이 문제는 동쪽의 N개의 사이트를 고르는 문제로 바뀌게 됩니다. 즉 mCn의 조합을 구하면 되는 것이 되는 것이죠.

결국 이항 계수 문제와 동일한 점화식을 가지게 됩니다.

nm 1 2 3 4 5
1  1 2 3 4 5
2  x 1 3 6 10
3  x x 1 (1 + 3) (4 + 6)
4  x x x 1 (1 + 4)

f(n, m) = f(n, m - 1) + f(n - 1, m - 1)

코드

var cache = Array(repeating: Array(repeating: -1, count: 31), count: 31)

func f(_ n: Int, _ m: Int) -> Int {
    if n == 1 {
        cache[n][m] = m
    }
    
    if n == m {
        cache[n][m] = 1
    }
    
    if cache[n][m] < 0 {
        cache[n][m] = f(n, m - 1) + f(n - 1, m - 1)
    }
    
    return cache[n][m]
}

let T = Int(readLine()!)!

for _ in 0..<T {
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    print(f(input[0], input[1]))
}