문제
풀이
처음에는 long long int 를 통해 구하려고 했는데 결과 값이 long long int 로는 택도 없이 크다.
70 C 30 의 값이 55347740058143507128으로 20자리나 되는데 long long int 형의 범위는
–9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 으로 19자리 이다.
해결방법은 string을 사용하는 것이다.
숫자를 string으로 저장한 후, string 끼리 더할 때 1의 자리 부터 순서대로 더해가면 된다.
조합 값을 구할 때는 파스칼 삼각형 기법을 사용하였고 memoization을 통해 실행 속도를 높였다. 파스칼삼각형은 아래의 링크를 참조하자.
파스칼 삼각형의 자세한 설명
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <string>
#include <algorithm> // reverse 함수
using namespace std;
int n, m;
string factorial[101][101];
string bigNumAdd(string n1, string n2)
{
int sum = 0;
string result;
// 1의 자리부터 더하기
while (!n1.empty() || !n2.empty() || sum)
{
if (!n1.empty())
{
sum += n1.back() - '0';
n1.pop_back();
}
if (!n2.empty())
{
sum += n2.back() - '0';
n2.pop_back();
}
result.push_back((sum % 10) + '0');
sum /= 10;
}
// 1의 자리부터 push 했으므로 뒤집어준다.
reverse(result.begin(), result.end());
return result;
}
string combination(int n, int r)
{
if (n == r || r == 0)
return "1";
string &result = factorial[n][r]; // 참조형 변수
// 이미 계산했으면 바로 return, memoization 기법
if (result != "")
return result;
// 파스칼삼각형 원리 이용
result = bigNumAdd(combination(n - 1, r - 1), combination(n - 1, r));
return result;
}
void input()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
}
int main()
{
//input 받기
input();
// 조합 구하기
cout << combination(n, m);
return 0;
}
