[백준]1256_사전

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

Solved

✔ 알고리즘 분류: DP, 조합론
✔ 총 경우의 수는 ${_{n+m}C_m}$이다.
✔ $\binom{n}{k}$ = ${_nC_k}$ = $\frac{n!}{(n-k)!k!}$ 을 사용해 푸는 것은 20! = 51,090,942,171,709,440,000 으로, long의 최대값 9,223,372,036,854,775,807도 가뿐히 넘으므로 불가능하다. 그러니 웬만한 이항계수 문제는 파스칼의 삼각형 $\binom{n}{k}$ = $\binom{n-1}{k}$ + $\binom{n-1}{k-1}$ 을 이용하여 풀자.(DP)

using namespace std;
#include <iostream>
#include <vector>
#include <cstring>
#define INF 1000000010

int dp[101][101];
//dp[i][j] = a개수 i, z개수 j일 때 나올 수 있는 조합의 수

int getAZ(int a, int z) {
	if (a == 0 || z == 0) return 1;
	if (dp[a][z] != -1) return dp[a][z];
	dp[a][z] = getAZ(a - 1, z) + getAZ(a, z - 1);
	if (dp[a][z] >= INF) dp[a][z] = INF;
	return dp[a][z];
}

string solve(int a, int z, int c) {
	//a,z: 사용가능한 a,z의 수
	//c번째 문자열을 구하자
	string answer = "";
	int total = a + z;
	for (int i = 0; i < total; i++) {
		if (a > 0) {
			int tmp = getAZ(a-1,z);
			if (tmp < c) {
				answer += 'z';
				c -= tmp;
				z--;
			}
			else {
				answer += 'a';
				a--;
			}
		}
		else {
			answer += 'z';
		}
	}
	return answer;
}
int main() {	
	int a, z, c;
	cin >> a >> z >> c;
	vector<char> v;

	memset(dp, -1, sizeof(dp));
	if (c > getAZ(a,z)) {
		cout << "-1\n";
		return 0;
	}

	cout << solve(a, z, c) << '\n';
	return 0;
}