문제 링크 (opens new window)

풀이

1. 조합 계산을 DP로 풀이
2. 조합에서의 파스칼 삼각형 공식으로 DP 풀이

import Foundation

// mCn = m-1Cn + m-1Cn-1
func combination(_ m: Int, _ n: Int) -> Int {
    var dp: [[Int]] = .init(repeating: .init(repeating: 1, count: m+1), count: m+1)

    for i in 1...m {
        for j in 0...i {
            if i == j || j == 0 {
                dp[i][j] = 1
                continue
            }

            dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
        }
    }

    return dp[m][n]
}

let T = Int(readLine()!)!

for _ in 0..<T {
    let NM = readLine()!.split(separator: " ").map { Int($0)! }; let N = NM[0]; let M = NM[1]
    print(combination(M, N))
}