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;
}