백준 1256: 사전

문제 요약

사전에 수록되어 있는 모든 문자열은 N개의 "a"와 M개의 "z"로 이루어져 있다. 그리고 다른 문자는 없다. 사전에는 알파벳 순서대로 수록되어 있다.

N과 M이 주어졌을 때, K번째 문자열이 무엇인지 구하는 프로그램을 작성하시오.

문제 분류

• 다이나믹 프로그래밍

문제 풀이

우선 2차원 배열의 DP를 구성한다. dp[n][m]은, n개의 a와 m개의 z를 사용하여 만든 문자열의 개수이다.

이렇게 구성한 2차원 DP배열을 이용하여 k번째의 문자열을 만들면 된다. dp[n][m]의 점화식은 dp[n][m] = dp[n - 1][m] + dp[n][m - 1]로 나타낼 수 있다. 즉, a로 시작하는 경우의 수와 z로 시작하는 경우의 수의 합으로 표현한 것이다. 이를 k와 비교하면 된다.

a로 시작하는 경우의 수가 k보다 작거나 같다면, 해당 k번째 문자열은 a로 시작한다는 것을 알아낼 수 있다. 그렇지 않다면 해당 문자열은 z로 시작한다. 이 경우에는 k를 dp[n - 1][m]으로 빼주어야 하는데, dp[n][m]의 k번째는 dp[n][m] = dp[n - 1][m] + dp[n][m - 1]에 의해 dp[n][m - 1]안에서 k - dp[n - 1][m]과 같기 때문이다.

n 혹은 m이 0이 될 때까지 반복한 후, 남는 n과 m에 대해 a혹은 z를 뒤에 붙여주면 된다.

참, dp[n][m]이 k보다 크면 -1을 출력하면 된다. 가짓수가 int 범위를 초과하므로 unsigned long long의 자료형으로 설정해주었다.

풀이 코드

#include <stdio.h>
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
unsigned long long dp[101][101];

unsigned long long sol(int n, int m)
{
	if (dp[n][m]) return dp[n][m];
	if (!n || !m) dp[n][m] = 1;
	else dp[n][m] = sol(n - 1, m) + sol(n, m - 1);
	
	return dp[n][m];
}

int main()
{
	int k;
	scanf("%d%d%d", &n, &m, &k);
	sol(n, m);
	
	if (k > sol(n, m)) cout << -1;
	else {
		string res;
		while (m > 0 && n > 0) {
			if (dp[n - 1][m] >= k) {
				res += 'a';
				n--;
			}
			else {
				res += 'z';
				k -= dp[n - 1][m];
				m--;
			}
		}
		while (n > 0) {
			res += 'a';
			n--;
		}
		while (m > 0) {
			res += 'z';
			m--;
		}
		cout << res;
	}
}