백준 1256 사전

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 a와 z로만 이루어진 단어가 사전순으로 정렬 되있을때 K번째 단어를 찾는 문제입니다.

 

a,z가 최대 100개이고 K가 10억개이므로 단순히 개수를 세는 방법으로 해결이 불가능합니다.

 

문제를 해결하기 위해서 저는 먼저 2차원 배열에 a가 i개 z가 j개 있을때 나오는 조합의 개수를 저장하였습니다. 

 

식을 세워보면 dp[i+1][j] = dp[i][j] * (i+j+1) / (i+1)

                   dp[i][j+1] = dp[i][j] * (i+j+1) / (j+1) 과 같은 식으로 개수를 구할 수 있습니다.

 

각 조합의 개수를 구한다음 이제 K번째 단어를 찾아야 하는데 문자를 앞에서부터 하나씩 붙이면서 K에서 개수를 제하는 방법으로 구할 수 있습니다. findfunc(findfunc(int N, int M, int length) 이라는 함수를 만드는데 a가 N개 남았고 z가 M개 남았고 찾아야 하는 길이가 length만큼 남았다는 의미로 볼 수 있습니다. 이때 dp[N-1][M] 의 값을 기준으로 a를 붙일지 z를 붙일지 판단 할 수 있는데 저 값이 length 보다 크거나 같으면 a를 붙이고 그렇지 않으면 z를 붙여주면 됩니다. 이후 붙인 문자에 따라 N,M값을 줄이고 재귀적으로 함수를 호출하면 됩니다.

 

아래는 코드입니다.

#include <iostream>
#include <string>
#include <cstring>

using namespace std;
#define MAX 1000000000

long long dp[110][110];
string ans;

void findfunc(int N, int M, int length) {

    if(N == 0) {
        for(int i = 0 ; i< M; i++)
            ans += 'z';
        return;
    }
    if(M == 0) {
        for(int i = 0; i < N; i++)
            ans += 'a';
        return;
    }

    if(dp[N-1][M] >= length) {
        ans = ans + 'a';
        findfunc(N-1, M, length);
    }
    else {
        ans = ans + 'z';
        findfunc(N, M-1, length - dp[N-1][M]);
    }
    return;
}

int main(void) {
        int N,M,K; cin >> N >> M >> K;

        dp[1][1] = 2;

        for(int i = 0; i <= 100; i++)
            for(int j = 0; j <= 100; j++) {
                if(i == 0 || j == 0) {
                    dp[i][j] = 1;
                    continue;
                }

            long long a = dp[i][j] * (i+j+1) / (i+1);
            long long b = dp[i][j] * (i+j+1) / (j+1);

            dp[i+1][j] = a <= MAX ? a : MAX+1;
            dp[i][j+1] = b <= MAX ? b : MAX+1;
        }

        if(dp[N][M] < K)
            cout<<-1;
        else {
            findfunc(N,M,K);
            cout<<ans<<'\n';
        }
    return 0;
}