문제
nCm을 출력한다.
입력
n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n)
출력
nCm을 출력한다.
풀이
nCm은 파스칼 점화식 C(n, m) = C(n - 1, m - 1) + C(n - 1, m)으로 계산할 수 있다. 현재 코드는 이 점화식을 재귀 + 메모이제이션으로 구현해서 같은 조합값을 반복해서 다시 구하지 않도록 했다.
값이 커질 수 있기 때문에 __uint128_t 배열에 결과를 저장하고, 마지막에는 계산된 큰 수를 그대로 문자열 형태에 맞춰 출력한다. 핵심은 조합을 직접 곱셈과 나눗셈으로 풀기보다, 작은 조합값들을 쌓아 올리는 구조로 바꾸는 것이다.
코드
#include <iostream>
#include <cmath>
using namespace std;
int n, m;
string result;
__uint128_t C[101][101];
//이거 없이 그냥 함수만 돌리면 무수히 많은 재귀가 증식해서 시간초과남
void input() {
cin >> n >> m;
}
__uint128_t com(int x, int y) {
if (C[x][y] != 0) return C[x][y];
if (y == 0 || x == y) return C[x][y] = 1;
if (y == 1 || x - y == 1) return C[x][y] = x;
if (x - y < y) y = x - y;
return C[x][y] = (com(x - 1, y - 1) + com(x - 1, y));
}
void solve() {
input();
__uint128_t r = com(n, m);
string front = to_string((long long) (r / (__uint128_t) pow(10, 15)));
string back = to_string((long long) (r % (__uint128_t) pow(10, 15)));
if(front == "0")
result = back;
else
result = front + back;
cout << result << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
solve();
return 0;
}복잡도
- 시간 복잡도: 메모이제이션으로 조합 상태를 한 번씩 계산하므로 이다.
- 공간 복잡도: 조합값 DP 배열을 저장하므로 이다.
마무리
nCm은 파스칼 점화식 C(n, m) = C(n - 1, m - 1) + C(n - 1, m)으로 계산할 수 있다.
