[백준] 1256-사전(C++)

문제링크:www.acmicpc.net/problem/1256

1256번: 사전

 

dp 문제였습니다.

 

우선 규칙성을 이해하기 위해 n과 m 개수에 따른 경우의 수를 생각해봤습니다.

z/a	0	1	2	3
0	0	1	1	1
1	1	2	3	4
2	1	3	6	10
3	1	4	10	20

즉 경우의 수는 dp[i][j] = dp[i][j-1] + dp[i-1][j] 입니다. 

 

 

이때 어떠한 규칙으로 az의 조합이 결정되는지 생각해보겠습니다.

 

ex) 2 2 2 일 경우

dp[2][2] = 6이고 dp[2][1], dp[1][2] = 3 이다. 2번째 문자열일 경우 첫문자는 a가 되고 dp[2][1]에 속하게 된다. 

dp[2][1]에서도 2번째 문자열이다. dp[1][1] = 2, dp[2][0] = 1 이므로 두번째 문자는 z가 되고 dp[1][1]에 속하게 된다.

이런 형태로 반복하면 azaz가 된다.

 

for(int i=0;i<n+m;i++) {
		int a_start = dp[a_cnt - 1][z_cnt];
		int z_start = dp[a_cnt][z_cnt - 1];

		//cout << a_start << endl;
		if (a_cnt == 0) {
			cout << 'z';
			z_cnt--;
			continue;
		}
		else if (z_cnt == 0) {
			cout << 'a';
			a_cnt--;
			continue;
		}

		if (k <= a_start) {
			cout << 'a';
			a_cnt--;
		}
		else {
			k = k - a_start;
			cout << 'z';
			z_cnt--;
		}


	}

위와 같은 형태로 진행해주면 된다.

 

한가지 조심해야할 점은 K는 1,000,000,000보다 작거나 같은 자연수라는 점이다. 나도 이 부분 때문에 꽤 애먹었다. 

k가 10억이기 때문에 n과 m의 경우의수 int형의 범위는 물론이고 long long의 범위를 쉽게 넘어가는 경우가 발생한다. 

이 때 오버플로우에 의해서 음수가 저장되며  경우의 수 값이 달라질 수 있기 때문에 1,000,000,000이 넘어가면 그냥 1,000,000,000을저장하여 문제를 해결하였다.  어차피 1,000,000,000번째 까지의 문자열을 확인해줄거기 때문에 값이 더 클 때 1,000,000,000이라고 저장하는게 유효한 것이다. 어차피 그러면 앞에 a인 것을 동일하기 때문이다.

이거를 이해하는데 오래 걸렸다. ㅠㅠ

 

정답코드입니다.

 

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;



int n = 0, m = 0;
int k = 0;

long long dp[101][101];




int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m >> k;

	for (int i = 1; i <= 100; i++)
		dp[i][0] = 1, dp[0][i] = 1;

	for (int i = 1; i <= 100; i++)
		for (int j = 1; j <= 100; j++) {
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
			if (dp[i][j] > 1000000000) dp[i][j] = 1000000000;
		}
	
	int a_cnt = n;
	int z_cnt = m;
	if (dp[n][m] < k) {
		cout << -1 << endl;
		return 0;
	}
		
	for(int i=0;i<n+m;i++) {
		int a_start = dp[a_cnt - 1][z_cnt];
		int z_start = dp[a_cnt][z_cnt - 1];

		//cout << a_start << endl;
		if (a_cnt == 0) {
			cout << 'z';
			z_cnt--;
			continue;
		}
		else if (z_cnt == 0) {
			cout << 'a';
			a_cnt--;
			continue;
		}

		if (k <= a_start) {
			cout << 'a';
			a_cnt--;
		}
		else {
			k = k - a_start;
			cout << 'z';
			z_cnt--;
		}


	}

	cout << "\n";
	return 0;
}