[C++]백준 - 2407번 문제

2407번: 조합 (acmicpc.net)

2407번: 조합

 

2407번 : 조합

---

nCm을 출력한다.

 

입력

---

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

 

 

출력

---

nCm을 출력한다.

 

 

---

 

생각해 볼 점

---

예제 출력을 보아하니 출력값은 int 범위(21억)는 가볍게 넘고,

 

long long도 충분히 넘어갈 것 같습니다.

 

C++로 해결하고 싶다면, string을 이용해 덧셈을 처리하는 함수가 필요합니다.

 

덧셈은 사람이 수동으로 더하는 과정을 그대로 구현합니다.

 

다음은 nCm을 구하는 방법입니다만, 파스칼의 삼각형을 이용합니다.

 

파스칼의 삼각형

 

 

nCm = n-1Cm-1 + n-1Cm 입니다.

 

이를 이용하면 DP를 통해 조합을 구해낼 수 있습니다.

 

코드

---

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

string dp[100][101];

//string 덧셈 함수
string add(string A, string B)
{
	//A의 자리수가 더 크면 Swap
	if (A.size() > B.size())
	{
		string temp = A;
		A = B;
		B = temp;
	}

	//오른쪽부터 계산 rbegin()
	auto a_it = A.rbegin();
	auto b_it = B.rbegin();
	string ret = "";

	//올림수
	bool carry = false;

	//오른쪽부터 한자리 씩 계산
	for (; a_it != A.rend(); a_it++)
	{
		char n = *a_it - '0' + *b_it + carry;
		carry = false;

		//올림
		if (n > '9')
		{
			n -= 10;
			carry = true;
		}
		*b_it = n;
		b_it++;
	}

	//남은 자릿수 계산
	for (; b_it != B.rend(); b_it++)
	{
		*b_it += carry;
		carry = false;
		if (*b_it > '9')
		{
			*b_it -= 10;
			carry = true;
		}
	}
	
	//올림이 남아있으면 맨 앞에 1 추가
	if (carry)
		B = "1" + B;
	return B;
}


//동적 계획법을 이용한 조합 계산 함수
string func(int const& n, int const& m)
{
	if (!dp[n][m].empty())
		return dp[n][m];
	if (m == 0 || m == n)
		return dp[n][m] = "1";
	return dp[n][m] = add(func(n - 1, m - 1), func(n - 1, m));
}

int main()
{
	int N, M;
	scanf("%d %d", &N, &M);

	for (int i = 0; i < 100; i++)
		fill_n(dp[i], 101, "");
	dp[0][0] = "1";
	cout << func(N, M);
	return 0;
}

 

그 외

---