백준 2407번 조합 Swift

https://www.acmicpc.net/problem/2407

2407번: 조합

 

내 코드

import Foundation

func combination(_ N: Int, _ M: Int) -> Decimal {
    var result = Decimal(1)
    let m = min(M, N - M)
    if m == 0 {
        return 1
    }
    for i in 1...m {
        result *= Decimal(N - i + 1)
        result /= Decimal(i)
    }
    return result
}

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let N = input[0]
let M = input[1]

print(combination(N, M))

---

Review

알고리즘을 풀면서 Decimal이라는 큰 수를 다루는 자료형은 처음 써봤습니다.
UInt64의 범위도 넘어가길래 더 큰 자료형이 필요했습니다.

Decimal 자료형의 범위는 
10의 -128승부터 10의 127승입니다.

처음에는 숫자 크기를 생각하지 않고 풀었습니다.

참고로 첫 번째 else 블록 안에 있는 if else 부분은
let m = min(m, n - m)로 해결할 수 있었습니다.

// 틀린 풀이

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let N = input[0]
let M = input[1]

if N == M {
    print(1)
} else {
    if N/2 >= M {
        let a = ((N-M+1)...N).reduce(1, *)
        let b = (1...M).reduce(1, *)
        print(a/b)
    } else {
        let a = ((M+1)...N).reduce(1, *)
        let b = (1...(N-M)).reduce(1, *)
        print(a/b)
    }
}

당연하지만 1... 49.reduce(1, *) 은 Int 자료형을 가볍게 넘어가기 때문에 해결하지 못했습니다.

---

그러면 그냥 Decimal 타입으로 바꿔서 고차 함수 쓰면 안 되나? 🤔

-> 물론 Decimal로 변경해서 한 번에 해도 되나, 큰 수들의 나눗셈에 소수점 이슈가 있었습니다.

따라서 한 번에 모두 계산해서 큰 수를 나누는 게 아닌
for 문을 사용하여 각각 한 번씩 여러 번 연산을 진행하는 게
더 정확한 값이 나올 것이라고 생각했습니다.

for i in 1...m {
    result *= Decimal(n - i + 1)
    result /= Decimal(i)
}

이렇게 하면 100c49라는 식도 좀 더 작은 수로 연산을 할 수 있습니다.

---

 

이 문제는 DP로도 풀 수 있는 방법이 있습니다.

조합 공식을 보면 C(n, m)은 C(n−1,m−1)+C(n−1,m) 라는 점화식을 가지고 있어서 DP 테이블로도 가능합니다.
물론 DP 테이블에 있는 수가 크기 때문에 이번에도 Decimal을 사용했습니다.

import Foundation

func combinationDP(N: Int, M: Int) -> Decimal {
    var dp = Array(repeating: Array(repeating: Decimal(0), count: M+1), count: N+1)

    // C(n, 0) = 1, C(n, n) = 1
    for i in 0...N {
        dp[i][0] = 1
        if i <= M { dp[i][i] = 1 }
    }

    for i in 1...N {
        for j in 1...min(i, M) {
            if j != i {
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
                // C(n, m) = C(n−1, m−1) + C(n−1, m)
            }
        }
    }

    return dp[N][M]
    // dp = [[1, 0, 0, 0], [1, 1, 0, 0], [1, 2, 1, 0], [1, 3, 3, 1], [1, 4, 6, 4], [1, 5, 10, 10]]
    // dp[5][3] = 10
}

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let N = input[0]
let M = input[1]

print(combinationDP(N: N, M: M))

 

Swift 문제를 풀면서 큰 수를 처음 다뤄보는 경험이 되었습니다.

시간 복잡도가 아닌 큰 수로 알고리즘을 풀면서 런타임 에러를 접했습니다.
큰 수로도 에러가 뜰 수 있다는 걸 알고리즘을 풀며 느꼈습니다.