백준 1256번 사전

문제 링크입니다: https://www.acmicpc.net/problem/1256

DP 문제였지만 DP만으로는 풀 수 없고 quickSearch 알고리즘처럼 몇번 skip, 즉 건너뛰어야하는지 파악하면서 푸는 문제였습니다.

우선, DP를 이용해 'a'와 'z'를 조합해 만들 수 있는 단어들의 갯수를 구합니다.

(간단한 방법으로는 factorial(A+Z)/(factorial(A)*factorial(Z))를 통해 갯수를 구할 수 있지만 DP를 사용하지 않을 경우 시간초과가 발생합니다.)

만약, 여기서 구한 단어들의 갯수가 K가 더 크다면 해당 단어가 존재하지 않는다는 증거이므로 noWord=true가 됩니다.

그 다음 getWord 함수를 통해 K번째 단어를 구하는데 'a'와 'z' 둘 다 더하지 못하는 경우는 해당 단어가 존재하지 않는다는 증거이므로 noWord=true가 됩니다.

#include <iostream>

#include <string>

#include <algorithm>

#include <cstring>

using namespace std;

 

const int MAX = 100 + 1;

 

int N, M, K;

string word;

bool noWord;

int cache[MAX][MAX];

 

int possibleNumOfWord(int A, int Z)

{

        //기저 사례

        if (A == 0 || Z == 0)

                 return 1;

 

        int &result = cache[A][Z];

        if (result != -1)

                 return result;

 

        //a를 택할 경우와 z를 택할 경우 모두 고려

        //1,000,000,000을 넘으면 조건 충족하는 단어 X

        result = min(possibleNumOfWord(A - 1, Z) + possibleNumOfWord(A, Z - 1), 1000000000 + 1);

        return result;

}

 

void getWord(int A, int Z, int skip)

{

        //z만 남았을 경우

        if (A == 0)

        {

                 for (int i = 0; i < Z; i++)

                         word += 'z';

                 return;

        }

        //a만 남았을 경우

        if (Z == 0)

        {

                 for (int i = 0; i < A; i++)

                         word += 'a';

                 return;

        }

 

        int idx = possibleNumOfWord(A - 1, Z); //a를 맨 앞에 택하였을 경우 가능한 조합의 수

        //그 경우의 수보다 건너뛰어야할 수가 적다면 a 추가

        if (skip < idx)

        {

                 word += 'a';

                 getWord(A - 1, Z, skip);

        }

        //그 경우의 수보다 건너뛰어야할 수가 크고 1,000,000,000보다 같거나 작다면 z 추가

        else  if (skip <= 1000000000)

        {

                 word += 'z';

                 getWord(A, Z - 1, skip - idx);

        }

        else //a와 z 모두 추가 불가능하므로 조건 성립하는 단어가 없다

                 noWord = true;

}

 

int main(void)

{

        cin >> N >> M >> K;

       

        noWord = false;

        memset(cache, -1, sizeof(cache));

 

        if (K > possibleNumOfWord(N, M)) //조건을 만족하는 단어들의 개수보다 큰 K번째 단어를 구할 수 없다

                 noWord = true; //조건 성립하는 단어가 없다

        else

                 getWord(N, M, K - 1); //K - 1번 건너 뛴 단어를 구한다

 

        if (noWord) //조건 성립하는 단어가 없을 경우

                 cout << -1 << endl;

        else

                 cout << word << endl;

 

        return 0;

}