백준 2407번 C++

백준 2407번 조합

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

2407번: 조합

정답 코드

#include <vector>
#include <string>
#include <iostream>

#define MOD 1000000000000000

using namespace std;

int n, m;
long long dp1[101][101], dp2[101][101];

int main() {
	cin >> n >> m;

	dp1[0][0] = 1;

	for (int i = 1; i <= n; i++) {
		dp1[i][0] = 1;
		for (int j = 1; j <= i; j++) {
			dp1[i][j] = dp1[i - 1][j] + dp1[i - 1][j - 1];
			dp2[i][j] = dp2[i - 1][j] + dp2[i - 1][j - 1];

			dp2[i][j] += dp1[i][j] / MOD;
			dp1[i][j] %= MOD;
		}
	}

	if (dp2[n][m] == 0) {
		cout << dp1[n][m] << '\n';
	}
	else {
		cout << dp2[n][m] << dp1[n][m] << '\n';
	}
}

문제 풀이

얼핏 보면 간단한 문제일수도 있지만 의외로 생각해야 할 점이 있습니다. 자료형의 크기를 long long형으로 해도 오버플로우가 발생합니다. 문자열로 계속해서 표현하는 방법도 있지만 조금 복잡해서 dp를 이용해서 풀었습니다.