백준 - 다리 놓기 (1010)

var dp = Array(repeating: Array(repeating: 0, count: 31), count: 31)

// dp 테이블 초기화
for i in 1..<dp.count {
    dp[i][0] = 1
    dp[i][1] = i
    dp[i][i] = 1
}

// dp 테이블 채우기
for i in stride(from: 2, to: dp.count, by: 1) {
    for j in stride(from: 1, to: i, by: 1) {
        dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
    }
}

// 질의 수행
let T = Int(readLine()!)!

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

M개의 사이트에 N개의 다리를 겹치지 않고 놓는다는 것은 M개에서 N개를 선택하는 의미이다. 따라서 일반적인 조합 문제처럼 DP 테이블을 만들면 쉽게 풀 수 있다.