🖊️ 문제

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

---

🖊️ 풀이

하...

아무 생각 없이 팩토리얼이지! 했는데
당연히 안됨..
시간복잡도 최악 of 최악인 팩토리얼을 어딜 감히 ,,

그래서 사용할 거는 dp

nCr = n-1Cr-1 + n-1Cr

이렇게 수제로.. 그려보면 알 수 있다

위의 두 값을 더하면 아래 값이 나온다
이 값들을 저장해주면 dp로 풀 수 있다.

근데 이 문제는 dp가 문제가 아니다 ..ㅋㅋㅋ

100C50이 나오면 long long으로도 커버가 안된다.
그래서 string을 이용해서 연산해준다.

string에 숫자들을 저장해놓고,
일의 자리 수부터 int로 바꿔서 더해주며 연산하고 자리 수마다 string으로 변환한다.
일의 자리수부터 연산해줬으니 다시 거꾸로 정렬해주면 문자열 연산 끝
(문자열 연산은 아래 코드를 보는게 더 직관적일듯)

그렇게 해주면 된다!

비록 나는 .. 못풀어서 구글링햇다...
실딱 이수민
수고요

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string dp[101][101];

int main()
{
	int n, m;
	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= i; j++) {
			if (j == 0 || j == i) dp[i][j] = "1";
			else {
				string s1 = dp[i - 1][j - 1];
				string s2 = dp[i - 1][j];
				int sum = 0;
				string s3;

				while (!s1.empty() || !s2.empty() || sum) {
					if (!s1.empty()) {
						sum += s1.back() - '0';
						s1.pop_back();
					}
					if (!s2.empty()) {
						sum += s2.back() - '0';
						s2.pop_back();
					}
					s3.push_back((sum % 10) + '0');
					sum /= 10;
				}
				reverse(s3.begin(), s3.end());
				dp[i][j] = s3;
			}
		}
	}
	cout << dp[n][m] << endl;
}

---

참고
https://codecollector.tistory.com/977
https://rujang.tistory.com/entry/%EB%B0%B1%EC%A4%80-2407%EB%B2%88-%EC%A1%B0%ED%95%A9-CC