백준 2407 - 조합(C++)

문제

nCm을 출력해라.

 

입력

n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤100, m ≤ n)

 

예제 입력

100 6

 

예제 출력

1192052400

 

문제 해결

어디서 힌트를 얻을 수 있을까?

 

'nCm'과 '조합'이라는 키워드를 보았을 때 나는 이항 계수를 떠올렸다.

 

그리고 수많은 반복되는 중복 문제를 고려하여 다이나믹 프로그래밍도 적용도 생각했다.

 

그리고 최대 범위의 조합의 수를 고려하면 커다란 범위의 수를 어떻게 처리해야 할 지도 고안해야 했다.

 

우선 하나하나 해결해보도록 해보자.

 

우선 이항 계수를 삼각형으로 표현한 파스칼의 삼각형의 점화식을 보도록 하겠다.

 

위의 점화식에 따라 커다란 틀을 구현할 수 있겠다.

 

그리고 메모이제이션은 다음과 같이 할 수 있다. (N, M)쌍에 값이 이미 갱신되어 있다면 값을 반환하고 아니면 값을 갱신하면 되는 것이다.

 

그리고 커다란 수는 어떻게 해결할 수 있을까?

 

이는 문자열로 계산하면 편하게 계산할 수 있다.

 

코드

#include <iostream>
#include <string>
#include <algorithm>

std::string cache[101][101];

std::string bigAdd(std::string n1, std::string n2)
{
	int sum = 0;
	std::string ret;

	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();
		}
		ret.push_back((sum % 10) + '0');
		sum /= 10;
	}
	std::reverse(ret.begin(), ret.end());
	return ret;
}

std::string combination(int N, int M)
{
	if (N == M || M == 0)
		return "1";
	std::string& ret = cache[N][M];
	if (ret != "")
		return ret;
	return ret = bigAdd(combination(N - 1, M - 1), combination(N - 1, M));
}

int main(void)
{
	int N, M;

	std::cin >> N >> M;
	std::cout << combination(N, M) << std::endl;
	return 0;
}

 

문제 출처

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

2407번: 조합

 

이론

https://ko.wikipedia.org/wiki/파스칼의_삼각형

파스칼의 삼각형 - 위키백과, 우리 모두의 백과사전

https://donggoolosori.github.io/2020/10/16/boj-2407/

[백준] 2407번 조합 - C++ - DGOS | 동꿀오소리