[DP] BOJ 1256_사전

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

1256번: 사전

중복조합과 관련된 dp문제이다.

a와 z를 통해 문자열을 만드는 것은 다음과 같이 생각할 수 있다.

i개의 a에 대해 바깥 공간을 포함한 사이 공간들에 j개의 j를 넣는 것으로 생각하면,

j개의 z를 i+1개의 공간에 넣는 가짓수가 된다. 따라서, iHj가 곧 구하는 만들 수 있는 총 문자열의 갯수가 된다.

 

중복조합을 계산하기 위해서는 팩토리얼이 섞인 식을 계산해야 하는데, 이 부분에서 dp를 활용할 수 있다.

굳이 증명하자면 중복조합은 다음과 같은 성질을 가진다. 이 부분을 dp로 활용하면,

nHm의 값을 빠르게 구할 수 있다. 즉, dp[n][m] = dp[n-1][m] + dp[n][m-1] 이다.

이렇게 구한 전체 문자열의 갯수에서, k번째 문자열은 어떻게 구해야 할까?

위의 예시와 같이 a 5개, z 4개로 만들어진 문자열을 사전 순으로 나열해보면

aaaaazzz, aaaazazzz, aaaazzazz, aaaazzzaz, aaaazzzza, aaazaazzz, aaazazazz, aaazazzaz, ...

z가 한칸씩 앞으로 당겨지며 정렬되는 것을 확인할 수 있다.

 

a n개, z m개로 이루어진 문자열에서 그림에서 붉은 색으로 칠한 부분처럼 a i개, z 1개 문자열을 고정시키면,

고정된 문자열을 제외한 나머지 부분으로 만들 수 있는 모든 문자열의 갯수는 곧 dp[a-i][m-1] 과 같다.

따라서 k번째 문자열을 구할 때, 누적합을 통해 k가 어느 고정된 문자열을 가지는지 확인하고,

고정된 문자열을 제외한 나머지 부분에서 k가 몇 번째인지 갱신해가며 문자열을 구하면 된다.

 

위의 n = 5, m = 4 인 예시에서 k = 58일 때, 고정된 문자열을 기준으로 k번째 문자열을 구해보자.

1. 맨 앞 문자열 : 모든 a를 앞에 쓴 뒤, 모든 z를 뒤에 씀 : aaaaazzzz (1개)

2. a를 4개, z를 1개 고정 : aaaaz|azzz

나머지 문자 a 1개, z 3개로 만들 수 있는 문자열의 갯수가 곧 aaaaz를 고정한 문자열의 갯수이다. 즉, dp[1][3] = 4이다.

3. a를 3개, z를 1개 고정 : aaaz|aazzz

나머지 문자 a 2개, z 3개로 만들 수 있는 문자열의 갯수가 곧 aaaz를 고정한 문자열의 갯수이다. 즉, dp[2][3] = 10이다.

4. dp[3][3] = 20

5. dp[4][3] = 35

6. dp[5][3] = 56

 

누적합을 통해 k = 58은 1~4까지의 누적합(35)과 1~5까지의 누적합(70) 사이에 있으므로,

k번째 문자열은 a를 4개 넘긴 az|aaaazzz 상태에서 만들 수 있는 문자열임을 알 수 있고, 따라서 앞의 az는 확정이다.

k는 1~4의 누적합 35번째 이후임을 알았으므로, 이제 남은 aaaazzz에 대해

k - 35 = 28번째 문자열을 구해 붙이면 된다. 

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
 
using namespace std;
 
int n, m;
unsigned long long k, dp[101][101]; //dp : a가 i개, z가 j개 있을 때 가능한 모든 문자열의 갯수
 
string getanswer() {
    int acnt = 0;
    long long acc = 0; 
    string answer = "";
 
    if (k > dp[n][m]) answer = "-1";
    else {
        while (1) {
            if (k == 1) {
                for (int i = 0; i < n; i++) answer += "a";
                for (int i = 0; i < m; i++) answer += "z";
                break;
            }
            if (k == dp[n][m]) {
                for (int i = 0; i < m; i++) answer += "z";
                for (int i = 0; i < n; i++) answer += "a";
                break;;
            }
            acnt = 0; acc = 0; 
            //dp누적합을 이용해 z 하나의 위치를 앞쪽으로 당겨가며 
            //z 이후의 문자열에 대한 dp값을 통해 z의 위치 결정
            for (int i = 0; i <= n; i++) {
                if (k <= acc + dp[i][m - 1]) { acnt = n - i; break; }
                acc += dp[i][m - 1];
            }
            //위치를 결정했다면, z의 위치까지 문자열은 확정임
            for (int i = 0; i < acnt; i++) answer += "a";
            answer += "z";
            //k값 갱신
            k -= acc;
            //n, m값 갱신
            n -= acnt; m--;
            if (k == 0) break;
        }
    }
    return answer;
}
 
void getdp() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
}
 
void init() {
    cin >> n >> m;
    cin >> k;
 
    for (int i = 0; i <= n; i++) dp[i][0] = 1;
    for (int i = 0; i <= m; i++) dp[0][i] = 1;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
    
    init();
    getdp();
    string answer = getanswer();
 
    cout << answer << '\n';
 
    return 0;
}