[백준] 사전 1256번 C++ 풀이

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

1256번: 사전

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
long long dp[101][101];
int N, M, K;
string res = "";
long long Count(int a, int z)
{
	if (a == 0 || z == 0)
		return 1;
	if (dp[a][z] != 0)
		return dp[a][z];

	return dp[a][z] = min(Count(a - 1, z) + Count(a, z - 1),(long long)1000000001);
}

void solve(int a, int z, int k)
{
	if (a == 0)
	{
		for (int i = 0; i < z; i++)
			res +="z";
		return;
	}
	if (z == 0)
	{
		for (int i = 0; i < a; i++)
			res+="a";
		return;
	}

	long long check = Count(a - 1, z);
	if (k > check)
	{
		res+= "z";
		solve(a, z - 1, k - check);
	}
	else
	{
		res+="a";
		solve(a - 1, z, k);
	}
}
int main(void)
{
	cin >> N >> M >> K;
	solve(N, M, K);

	if (Count(N,M) < K)
		cout << "-1";
	else
		cout << res;
        
       //아래는 혼자 그냥 dp배열 확인을 위한 코드 
	/*cout << endl << endl;

	for (int i = 0; i <= N; i++) {
		for (int j = 0; j <= M; j++)
			cout << dp[i][j] << " ";
		cout << endl;
	}*/
}

 

도통 이해가 안갔는데 아래 블로그가 큰 도움이 되었다..

아래 블로그의 설명을 참조하시길~

https://degurii.tistory.com/164