문제 이해 단계
수학에서 조합을 뜻하는 nCr에서 n과 r이 입력으로 들어올 때, 그 해답을 출력하는 문제.
문제 접근 단계
일반적으로 연산식을 구현하여 계산하라고 이 문제를 냈을 리는 없다.
예제에서 봤듯이 입력애 따라 출력이 엄청 커지는데,
연산 처리가 오래 걸려 시간초과가 뜰 가능성이 높다.
그래서 조합 공식 nCr = n-1Cr + n-1Cr-1을
메모라이즈기법(DP) 방식으로 구현하기로 하였다.
d [n][m]라는 2차원 저장공간을 두고 nCr = d [n][r]
이런 식으로 연산 값을 기억해 두기로 하였다.
그런데 한 가지 문제가 생겼다.
바로 연산 값이 엄청나게 크다는 것이다.
가장 큰 자료형인 long long int가
–9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807으로 19자리이다.
그런데 100 C50 = 100,891,344,545,564,193,334,812,497,256
로 19자리를 초과한다.
그래서 값들을 전부 문자열로 변환하여 계산하는 큰 수 덧셈 방식을 사용하여 구현하였다.
이 문제에서는 두 가지 핵심이 있다고 생각하는데
1. DP 방식으로 해당 문제를 바라볼 수 있는가?
2. 큰 수 덧셈으로 해당 문제를 구현할 수 있는가?
자세한 것은 밑에 코드에서 보여주겠다.
문제 구현 단계
string d[101][101];
string Dp(int x, int y) {
if (x == y || y == 0) return "1";
if (d[x][y] != "") return d[x][y];
string ans = Add(Dp(x - 1, y), Dp(x - 1, y - 1));
return d[x][y] = ans;
}위에서 설명한 조합 공식을 이용한 DP 함수이다.
매개변수로 x는 n, y는 m을 의미한다.
값이 저장되는 2차원 공간 d로 string으로 선언되어 있다.
nC0이 될 때와 두 수가 같을 때의 처리를 먼저 해주고,
이미 연산한 값은 바로 반환처리를 해준다.
그리고 Add란 함수의 매개변수로 Dp(x-1, y)와 Dp(x-1, y-1)을 넘겨준다.
이는 재귀함수의 반환 값을 큰 수의 덧셈
즉, String 끼리의 덧셈을 수행하는 함수를 수행하기 위함이다.
Add(Dp(x - 1, y), Dp(x - 1, y - 1)) 는
사실상 n-1Cr + n-1Cr-1을 뜻한다.
string Add(string num1,string num2) {
int size = max(num1.size(), num2.size());
int sum = 0;
string num = "";
for (int i = 0; i < size || sum; i++) {
if (num1.size() > i) sum += num1[i] - '0';
if (num2.size() > i) sum += num2[i] - '0';
num += sum % 10 + '0';
sum /= 10;
}
return num;
}큰 수 덧셈을 처리하는 Add 함수이다.
string 두 개를 매개변수로 받는다.
모든 배열을 다 훑기 위해서 size로는
둘 중 더 길이가 긴 거로 설정한다.
num에는 두 계산 결과가 string으로 저장될 것이기 때문에
""으로 초기화해 줬다.
반복문을 돌릴 때 i = 0부터 돌리는데,
1의 자리부터 순서대로 쌓겠다는 의미다.
즉 최종적으로 1의 자리부터 쌓이기 때문에
거꾸로 뒤집힌 상태가 되기 때문에 한번 뒤집어 줘야 한다.
num에는 (그 자리에 있던 값 + sum) % 10의 결과를 더한다.
올림수를 판단하기 위해, 10을 나눈 몫을 남겨두고 그 후에 연산에 사용한다.
이 과정을 반복한 후 num을 반환한다.
마지막으로 전체 코드를 올리고 설명을 마치겠다.
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string Add(string, string);
string Dp(int, int);
string d[101][101];
string Dp(int x, int y) {
if (x == y || y == 0) return "1";
if (d[x][y] != "") return d[x][y];
string ans = Add(Dp(x - 1, y), Dp(x - 1, y - 1));
return d[x][y] = ans;
}
string Add(string num1,string num2) {
int size = max(num1.size(), num2.size());
int sum = 0;
string num = "";
for (int i = 0; i < size || sum; i++) {
if (num1.size() > i) sum += num1[i] - '0';
if (num2.size() > i) sum += num2[i] - '0';
num += sum % 10 + '0';
sum /= 10;
}
return num;
}
int main() {
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int n, m;
cin >> n >> m;
string ans = Dp(n, m);
reverse(ans.begin(), ans.end());
cout << ans;
}앞서 설명했듯이 배열에는 string 값이 거꾸로 저장되어 있기 때문에
출력해 줄 때는 한번 뒤집어줘야 한다.
그래서 reverse로 한번 뒤집어 준 후 출력해 줬다.
시행착오
Dp를 세우는 것까진 어찌어찌했는데,
큰 수 덧셈은 한 번도 안 해봐서 정말 엄청나게 헤맸다.
인터넷을 참고해서 해봤는데 안 찾아봤으면 하기 어려웠을 거 같다.
근데 아직까지도 이해 안 가는데, 이거 실버 4문제라고?
내가 체감하기에는 그래프탐색 골드문제랑 비슷한데..?
내가 이상한 건가..?