[백준 / BOJ] C++ 2407 조합

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

2407번: 조합

풀이

조합 공식을 이용 - (nCm = n-1Cm-1 + n-1Cm)을 이용하여 값을 구한다.

 

long long을 사용해도 자료형 허용 범위를 넘어가는 미친 문제이다. 조합 공식쓰고 그냥 했다가 왜 안되지? 

하며 꽤나 헤매었던 문제...

Visual studio 2022 C++ 17 개발환경으로 long long으로 빌드하거나 디버깅하면 문제없이 다 출력이 된다.

 

그래서 오히려 헤메었다.. python에서는 자바의 Biginteger가 백그라운드에서 자동 지원이라서 string으로 구현하지않아도

문제없이 실행이 된다.

 

아무튼 아래 코드를 참조하자.

 

Code ( C++ )

#include <iostream>
#include <algorithm>

using namespace std;

string base[105][105] = {"0", };

string StringCalculate(string a, string b)
{
	int add = 0;
	string result;
	while (!a.empty() || !b.empty() || add)
	{
		if (!a.empty())
		{
			add += a.back() - '0';
			a.pop_back();
		}
		if (!b.empty())
		{
			add += b.back() - '0';
			b.pop_back();
		}
		result.push_back((add % 10) + '0');
		add /= 10;
	}
	reverse(result.begin(), result.end());

	return result;
}

string nCm(int n, int m)
{
	if (n == m || m == 0)
		return "1";

	if (base[n][m] != "")
		return base[n][m];

	return base[n][m] = StringCalculate(nCm(n - 1, m - 1), nCm(n - 1, m));
}




int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n, m;
	cin >> n >> m;
	cout << nCm(n, m);
}