[BOJ] 2407 조합 (C/C++)

2407번: 조합

문제

nCm을 출력한다.

입력

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

출력

nCm을 출력한다.

---

문제가 참 심플하다. 널리 알려져 있는 다음과 같은 점화식을 사용해서 쉽게 풀 수 있을 줄 알았다. 점화식이 이미 들통한 DP 문제만큼 쉬운 문제는 없다. 메모이제이션 + DP를 사용하면 간단하게 풀린다. 하지만 숫자가 너무 커서 이걸 문자열로 계산해야 하는 문제였다. 

 

$$(\genfrac{}{}{0ex}{}{n-1}{m-1})+(\genfrac{}{}{0ex}{}{n-1}{m})=(\genfrac{}{}{0ex}{}{n}{m})$$

 

문자열로 계산을 하다보니 그냥 출력하면 거꾸로 나온다. 그래서 출력을 뒤집어야 한다.

 

	#include <iostream>
	#include <string>
	using namespace std;
	int n, m;
	string C[101][101];
	string add(string n1, string n2) {
	string res = "";
	int len1 = n1.length();
	int len2 = n2.length();
	int len = len1 > len2 ? len1 : len2;
	int sum = 0;
	for (int i = 0; i < len || sum; i++) {
	if (len1 > i) sum += n1[i] - '0';
	if (len2 > i) sum += n2[i] - '0';
	res += (sum % 10) + '0';
	sum /= 10;
	}
	return res;
	}
	string Comb(int N, int M) {
	if (M == 0 || N == M) return C[N][M] = "1";
	if (C[N][M] != "") return C[N][M];
	return C[N][M] = add(Comb(N - 1, M - 1), Comb(N - 1, M));
	}
	int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> m;
	Comb(n, m);
	for (int i = C[n][m].length() - 1; i >= 0; i--)
	cout << C[n][m][i];
	return 0;
	}

view raw 2407.cpp hosted with ❤ by GitHub

후기)

문제가 그리 어렵지는 않았다. 하지만 수식을 문자열로 계산하는걸 진짜 오랜만에 해본 것 같다. 아마 1학년 때 기초 코딩 과목을 들으면서 였겠지...? 오랜만이라 감회가 새로웠다.