백준 2407번 조합 - SWIFT

문제

---

nCm을 출력한다.

 

입력

n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n)

 

출력

nCm을 출력한다.

 

문제 링크

2407번: 조합

 

 

풀이

---

BigInt가 지원되는 파이썬과 자바에서는 그냥 공식대로 곱해주면 답이 된다.

하지만 아쉽게도 Swift에서는 BInt라는 클래스를 어디서 구해오는 게 아니면 공식대로 풀 수 없다.

 

이항계수를 삼각형 모양으로 나열한 파스칼 삼각형에서 보면 주로 한 행의 가운데 부분이 가장 큼을 알 수 있다.

그래서 100 C 50이 대략 최댓값일 거 같아서 계산기로 계산을 돌려보니,

 

100891344545564193334812497256

 

라는 값이 나왔다.

 

Swift의 UInt64의 최댓값은

 

18446744073709551615

 

와 같으므로, 터무니없이 크다는 걸 알 수 있다.

 

이렇게 되면 절대로 한 번에 계산, 출력할 수 없게 된다.

 

그러면 어떻게 해야할까??

 

한 번에 계산, 출력할 수 없으니 값을 쪼개야한다.

 

우리는 아래의 값으로 값을 분할할 것이다.

 

1000000000000000000

 

이 수는 세어보면 총 19자리다.

그런데 UInt64는 20자리이다.

 

'이왕 쪼갤 거 20자리로 쪼개는 게 낫지 않나?'

 

그렇게 하면 런타임 에러가 난다.

 

그 이유는 아래에 나온다.

 

분할하는 과정

1. 일단은 수를 왼쪽과 오른쪽으로 나눠 놓는다.

물론 수는 1000000000000000000 를 기준으로 나눈다.▼

 

 

2. 그리고 이항계수 공식대로 계산을 진행해준다.

왼쪽은 0부터 시작하고, 오른쪽은 정상적으로 1부터 시작한다.

하지만 1000000000000000000 을 넘게 되면, 오른쪽 이항계수의 값에서 이 값을 빼버리고, 왼쪽에 동일한 이항계수 자리에 1을 더해준다. (오른쪽이 100 C 20 자리였다면, 왼쪽도 100 C 20 자리에 계산)

 

그렇게 되면 왼쪽에는 1000000000000000000 이상의 자릿수의 값만 모이게 되고, 오른쪽에는 그 이하의 자릿수의 값만 모이게 된다.▼

 

 

3. 이 계산이 끝나서 해당 자리의 이항계수에 도착하게 되면, 왼쪽의 이항계수의 수를 먼저 출력하고 오른쪽의 이항계수의 수를 이어서 출력하면 답이 나온다.

 

 

Swift 코드

---

let nm = readLine()!.split(separator: " ").map { Int(String($0))! }
let n = nm[0], m = nm[1]
let limit: UInt64 = 1000000000000000000
var left = [[UInt64]](repeating: [UInt64](repeating: 0, count: n + 1), count: n + 1)
var right = [[UInt64]](repeating: [UInt64](repeating: 0, count: n + 1), count: n + 1)

right[1][0] = 1
right[1][1] = 1

for i in 2...n {
    right[i][0] = 1
    right[i][i] = 1

    for j in 1..<i {
        right[i][j] = right[i - 1][j - 1] + right[i - 1][j]
        left[i][j] = left[i - 1][j - 1] + left[i - 1][j]

        if right[i][j] >= limit {
            right[i][j] -= limit
            left[i][j] += 1
        }
    }
}

if left[n][m] > 0 {
    print("\(left[n][m])" + "\(right[n][m])")
} else {
    print(right[n][m])
}