[BAEKJOON] 1256. 사전

Posted on April 07, 2021

문제 :

동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 김진영 조교는 동호와 규완이에게 특별 과제를 주었다. 특별 과제는 특별한 문자열로 이루어 진 사전을 만드는 것이다. 사전에 수록되어 있는 모든 문자열은 N개의 “a”와 M개의 “z”로 이루어져 있다. 그리고 다른 문자는 없다. 사전에는 알파벳 순서대로 수록되어 있다.

규완이는 사전을 완성했지만, 동호는 사전을 완성하지 못했다. 동호는 자신의 과제를 끝내기 위해서 규완이의 사전을 몰래 참조하기로 했다. 동호는 규완이가 자리를 비운 사이에 몰래 사전을 보려고 하기 때문에, 문자열 하나만 찾을 여유밖에 없다.

N과 M이 주어졌을 때, 규완이의 사전에서 K번째 문자열이 무엇인지 구하는 프로그램을 작성하시오.

입력 :

첫째 줄에 N, M, K가 순서대로 주어진다. N과 M은 100보다 작거나 같은 자연수이고, K는 1,000,000,000보다 작거나 같은 자연수이다.

출력 :

첫째 줄에 N, M, K가 순서대로 주어진다. N과 M은 100보다 작거나 같은 자연수이고, K는 1,000,000,000보다 작거나 같은 자연수이다.

풀이 :

지난 번에 풀어본 문제였지만 다시 풀어봐도 어려웠다!.. DP가 좀 감이 오는 것 같았는데, 다시 어려워지는 것 같다.

문제를 해결하고 나서 풀이를 정리하자면 key point는 두가지인 것 같다.

전형적인 memorization, 하지만 memorization을 활용해서 K번째 문자열을 재탐색해나가는 과정이 꽤나 까다로웠다.
memorization 배열의 크기를 long long 형으로 잡더라도 해당 범위를 넘어선 큰 수를 저장해야 한다. 여기서 포인트는 K가 1,000,000,000이하이기 때문에 최대값을 1,000,000,000보다 큰 값으로 맞춰주면 문제를 해결할 수 있다.

Memorization의 경우 행을 a의 갯수 열을 z의 갯수로 간주해서 dp[i][j] = a i개와 z j개로 만들 수 있는 조합 갯수를 저장한다.

여기서 2번에서 말한 것과 같이 long long형이 담을 수 없는 범위까지 저장되어 overflow가 일어나는데 그래서 최댓값을 정해둬야 한다.

문자열 재탐색의 경우 재귀 방식을 이용해 curidx + dp[i-1][j] ≥ findidx(찾으려는 문자열 인덱스)일 경우 ‘a’ 문자를 더해주고 그 외의 경우 ‘z’ 글자를 더해주는 방식으로 최종 문자열을 완성해 나갈 수 있다.

코드 :

코드 보기/접기

#include <iostream>
#include <string>
#include <algorithm>

#define MAX 1234567890
#define ll long long

using namespace std;
int findidx;
ll dp[101][101];

string findString(string curstr, int anums, int znums, int curidx) {
    if (!anums && !znums) return curstr;

    if (anums > 0 && curidx + dp[anums - 1][znums] >= findidx)
        return findString(curstr + 'a', anums - 1, znums, curidx);
    else
        return findString(curstr + 'z', anums, znums - 1, curidx + dp[anums - 1][znums]);
}

int main() {
    int n, m;
    cin >> n >> m >> findidx;

    dp[0][0] = 1;
    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] = min((ll) MAX, dp[i - 1][j] + dp[i][j - 1]);
    if (dp[n][m] < findidx) cout << "-1\n";
    else cout << findString("", n, m, 0) << '\n';
    return 0;
}

Algorithm

algorithm baekjoon C++