[백준] 사전

이 문제에서 요구하는 k번째 문자열을 찾기 위해서는 먼저 N,M개의 'a'와 'z'로 이루어진 문자열의 경우의 수를 구해야 한다.

경우의 수를 구하기 위해 백트래킹 알고리즘을 사용하였다.
N+M의 길이를 가지는 문자열을 각 위치에 문자를 '선택' 했을 경우 다음 위치의 문자에 대한 경우의 수를 재귀함수 형태로 다음 함수에게 넘기게 되며 최종적으로는 마지막 위치의 문자를 선택하게 되는데 이때는 앞의 모든 문자가 선택되어 있는 상태 이기 때문에 재귀호출 없이 완성된 문자열 의 개수 1을 반환하는 방식으로 탐색의 끝에서 부터 경우의 수를 추척하는 방식이다.

이때 이미 탐색했던 위치를 중복해서 탐색하게 되는데 dp[N][M] merix를 생성하여 이미 탐색했던 정보를 저장하여 탐색 시간을 절약할 수 있다.

이후 탐색이 끝난 dp의 정보를 토대로 K번째에 존재하는 문자열을 조합해 나가면된다.
문자열의 해당 위치에서 선택될수 있는 경우의 수는 2가지로 dp에서는 각 한가지를 선택했을 경우의 경우의 수가 저장되어 있다.

이때 'a'를 선택했을 때 경우의 수 >=K 가 성립했을 때 해당 위치의 문자는 'a'가된다.
반대로 'a'를 선택했을 때 겨우의 수 <K 가 성립했을 경우 해당 위치의 문자는 'z'가 되며 K = K - 'a'가 됬을 때의 경우의 수 로 다음 위치의 문자를 탐색해 나가면 된다.

단! 이때의 발생하는 모든 경우의 수는 long long 변수로 표현할 수 있는 수를 한참 띄어넘기 때문에 반드시 제한자를 주어야 한다.

#include <string>
#include <iostream>
#include <math.h>

using namespace std;

int N, M, K;
int dp[101][101]{};
string result;

int def(int a,int z) {
	
	if (z == 0 || a == 0) {
		dp[a][z] = 1;
		return 1;
	}

	if (dp[a][z] != 0)
		return dp[a][z];
    // K가 경우의 수를 초과할 경우의 핸들링시 최대값까지 비교할 수 있도록 하기 위해 +1한 값을 기준으로 했다.
	dp[a][z] =  min(1'000'000'001, def(a - 1, z) + def(a, z - 1));
	
	return dp[a][z];
}

void search(int a, int z,int k, string& result) {
	
	if (a == 0 && z== 0) return;

	if (a == 0) {
		result.push_back('z');
		search(a, z - 1, k, result);
	}
	else if (z == 0) {
		result.push_back('a');
		search(a - 1, z, k, result);
	}
	else if (a>0 && k <= dp[a - 1][z]) {
		result.push_back('a');
		search(a - 1, z, k, result);
	}
	else if(z>0){
		result.push_back('z');
		search(a, z - 1, k - dp[a - 1][z], result);
	}
}

int main() {

	cin >> N >> M >> K;

	if (K > def(N, M)) {
		cout << -1;
		return 0;
	}
	string result;
	search(N, M, K, result);
	cout << result;
}