[Algorithm] BOJ 1256 사전

문제 링크

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

문제 풀이

dp[x][y] : x개의 a와 y개의 z로 만들 수 있는 문자열 수

dp 배열에 a와 y의 갯수에 대해 만들 수 있는 문자열의 수를 저장해나가고, 구한 갯수를 기반으로 사전 순서를 고려하여 로직을 짰다.

x개의 a, y개의 z 로 단어를 만드는 경우는 아래와 같다.
1. x-1개의 a, y개의 z 로 만든 단어 앞에 a를 붙이는 경우
2. x개의 a, y-1 개의 z 로 만든 단어 뒤에 z를 붙이는 경우

따라서 dp[x][y] = dp[x-1][y] + dp[x][y-1] 라는 점화식을 유도할 수 있음

코드

#include <iostream>
#include <cstring>

using namespace std;

const int MAX = 101;

int n, m, k, noWord = 0;
string word;

// dp[x][y] : x개의 a와 y개의 z로 만들 수 있는 문자열 수
int dp[MAX][MAX];

int possibleNumOfWord(int a, int z) {
    // 기저에 도착하면 1 리턴
    if (a == 0 || z == 0) return 1;
    if (dp[a][z] != -1) return dp[a][z];

    // dp[x][y] = dp[x-1][y] + dp[x][y-1]
    dp[a][z] = min(possibleNumOfWord(a - 1, z) + possibleNumOfWord(a, z - 1), 1000000000 + 1);
    return dp[a][z];
}

// 정답이 될 단어 만들기
// a 개수, z 개수, 이전 순번
void getWord(int a, int z, int skip) {
    if (a == 0) {
        for (int i = 0; i < z; ++i) {
            word += 'z';
        }
        return;
    }
    if (z == 0) {
        for (int i = 0; i < a; ++i) word += 'a';
        return;
    }
    // a가 맨앞에 붙고 나머지 a-1, z 로 만들 수 있는 경우수
    int idx = possibleNumOfWord(a - 1, z);

    
    if (skip < idx) { // 맨앞에 a를 붙이는 경우 : 나머지 알파벳을 가지고 만든 skip 번째 문자열
        word += 'a';
        getWord(a - 1, z, skip);
    }
    else { // 맨앞에 z를 붙이는 경우 : a로 시작하는 idx개의 문자열보다 뒤에 있어서 skip - idx
        word += 'z';
        getWord(a, z - 1, skip - idx);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> m >> k;
    memset(dp, -1, sizeof(dp));
	
    // 만들 수 있는 단어의 갯수가 k보다 작으면 noWord = 1
    if (k > possibleNumOfWord(n, m)) noWord = 1;
    else getWord(n, m, k - 1);

    if (noWord) cout << -1;
    else cout << word;

    return 0;
}