(C++) [백준 2407번] 조합

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

2407번: 조합

 

solved.ac Class 4의 난이도 내림차순 정렬 기준 가장 쉬운 문제였던 조합이다.

Class 3을 다 풀고 와서 이것도 당연 어렵겠지? 하고 막상 난이도를 보니 실버더라.. 책정된 난이도와 내 난이도가 꼭 비례하지는 않는듯..ㅋㅋㅋ

 

파이썬처럼 큰 수를 언어에서 제공해주면 상관없는데 내가 푸는 C++은 long long 이상의 큰 수를 제공해주지 않아서, 방법이 2가지가 있었다. *아래는 풀이방법*

 

1. int__128을 써서 풀기: 이 방법이 직관적이긴 하지만 visual studio에서는 제공해주지 않아서 나는 시도하지 못했다.

2. string을 이용하기: string의 최대 길이는 운영체제마다 다르긴 해도 32비트라도 가정하면 2^32-1개이다. 아무리 큰 수라도 이정도의 길이를 필요로 하진 않아서 string으로 변환해서 푸는게 가능하다. 나는 이 방법을 사용했다.

 

우선 큰 수를 계산하는 함수를 하나 만들고, 파스칼의 삼각형을 이용하면 된다. 파스칼의 삼각형은 https://ko.wikipedia.org/wiki/%ED%8C%8C%EC%8A%A4%EC%B9%BC%EC%9D%98_%EC%82%BC%EA%B0%81%ED%98%95 여기 참고, 또한 https://donggoolosori.github.io/2020/10/16/boj-2407/ 이 분의 BigInteger 함수를 많이 참고했다. 나는 마지막 자리수끼리 더한걸 string으로 넘긴다고 생각했기 때문에 올림 처리를 어떻게 해야 할지 엄청 막막했는데 int 변수를 2개 만들어서 계산하고 /10과 %10을 이용하면 상당히 간단하고 쉬워진다는것을 알게 되었다.

nCm은 n-1Cm-1 + n-1Cm으로 나타낼 수 있으므로, 재귀와 메모이제이션 기법을 이용해서 풀 수 있다.

 

아래는 코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
typedef long long int ll;
string mem[105][105];
string BigInteger(string s1, string s2)
{
	int n1 = 0, n2 = 0;
	int sum = 0;
	string result = "";
	while (!(s1.empty() && s2.empty() && sum == 0))
	{
		if (!(s1.empty()))
		{
			n1 = s1.back() - '0';
			s1.pop_back();
		}
		if(!(s2.empty())) 
		{ 
			n2 = s2.back() - '0';
			s2.pop_back();
		}sum += (n1 + n2);
		result += to_string(sum % 10);
		sum /= 10;
		n1 = 0, n2 = 0;
	}
	reverse(result.begin(), result.end());
	return result;
}

string Pascal(int n, int m)
{

	if (n < 0 || m < 0) return "";
	if (n == m || m == 0) 
	{
		mem[n][m] = "1";
		return "1";
	}
	if (!mem[n][m].empty()) return (mem[n][m]);

	else
	{
		mem[n][m] = BigInteger(Pascal(n - 1, m - 1),Pascal(n - 1, m));
	}
	return mem[n][m];
}
int main()
{
	int n = 0, m = 0;
	string res;
	cin.tie(NULL);
	ios::sync_with_stdio(0);
	cin >> n >> m;
	res = BigInteger(to_string(n),to_string(m));
	res = Pascal(n, m);
	cout << res;
}