BOJ 1256 사전

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

문제

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

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

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

---

입력

첫째 줄에 세 정수 N, M, K가 순서대로 주어진다.

---

출력

첫째 줄에 규완이의 사전에서 K번째 문자열을 출력한다. 만약 규완이의 사전에 수록되어 있는 문자열의 개수가 K보다 작으면 -1을 출력한다.

---

제한

1 ≤ N, M ≤ 100
1 ≤ K ≤ 1,000,000,000

---

예제 입력 1

2 2 2

예제 출력 1

azaz

예제 입력 2

2 2 6

예제 출력 2

zzaa

… 이하 예제 생략

---

코드

1. a = 1개, z = 1개일 때 2가지
   • a z
   • z a
2. a = 1개, z = 2개일 때 3가지
   • a z z
   • z a z
   • z z a
3. a = 2개, z = 1개일 때 3가지
   • a a z
   • a z a
   • z a a
4. a = 2개, z = 2개일 때 6가지
   • a a z z
   • a z a z
   • a z z a
   • z a a z
   • z a z a
   • z z a a

여기서 알아차릴 수도 있으나 한 케이스를 더 해보면,

1. a = 2개, z = 3개일 때 10가지
   • a a z z z
   • a z a z z
   • a z z a z
   • a z z z a
   • ======
   • z a a z z
   • z a z a z
   • z a z z a
   • z z a a z
   • z z a z a
   • z z z a a

a = 2개, z = 3개일 때 생각해보면 a = 1개, z = 3개일 때 케이스 (4가지 경우)

• a z z z
• z a z z
• z z a z
• z z z a

앞에 a를 추가한 것들과 a = 2개, z = 2개일 때의 케이스 (6가지) 앞에 z를 추가한 것을 더한 것이 a = 2개, z = 3개의 경우의 수라는 것을 알 수 있다.

즉 a = n개, z = m개일 때의 경우의 수는

a = n - 1개, z = m개일 경우 + a = n개, z = m - 1개일 경우

와 같은 규칙이 있다는 것을 알 수 있다.

따라서 top-down 방식으로 a = n개, z = m개일 때의 경우의 수를 구하고, 구하는 과정 가운데 알게 된 각 단계의 경우의 수를 통해 K번 째 문자열을 구할 수 있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N, M, K;
    static int[][] dp;
    static StringBuilder answer = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        dp = new int[N + 1][M + 1];
        // 문자가 1가지만 있을 때 가능한 경우는 1가지이므로 1로 초기화
        for (int i = 1; i <= N; i++) dp[i][0] = 1;
        for (int i = 1; i <= M; i++) dp[0][i] = 1;
        // 그 외에는 아직 검사하지 않았다는 의미에서 MIN_VALUE로 초기화
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= M; j++) dp[i][j] = Integer.MIN_VALUE;

        // 검사 진행
        topDown(N, M);
        if(dp[N][M] < K) { // 검사 진행 후, 최대 경우의 수가 K보다 작으면 -1 출력
            System.out.println(-1);
            return;
        }

        findAnswer(N, M);
        System.out.println(answer);
    }

    // top-down 방식으로 우선 a와 z 각 문자 수에 따른 경우의 수를 계산
    static int topDown(int n, int m) {
        if(dp[n][m] != Integer.MIN_VALUE) return dp[n][m];
        dp[n][m] = topDown(n - 1, m) + topDown(n, m - 1);

        // K의 최대 경우의 수가 10억이므로, 10억 이상의 경우의 수는 10억으로 저장
        if(dp[n][m] > 1_000_000_000) dp[n][m] = 1_000_000_000;
        return dp[n][m];
    }

    // 정답을 찾는 것도 top-down 방식과 비슷하게 동작함
    static void findAnswer(int n, int m) {
        // 문자가 한 종류만 남았을 경우, 해당 문자의 개수만큼 정답 문자열에 추가 후 종료
        if(n == 0) {
            for (int i = 0; i < m; i++) answer.append('z');
            return;
        }
        if(m == 0) {
            for (int i = 0; i < n; i++) answer.append('a');
            return;
        }

        // a가 n - 1개, z가 m개인 경우의 수보다 작거나 같으면 answer에 a를 추가 후 검사 진행 
        if(dp[n - 1][m] >= K) {
            answer.append('a');
            findAnswer(n - 1, m);
        }
        /**
         * a가 n - 1개, z가 m개인 경우의 수보다 클 경우
         * a가 n개, z가 m - 1개인 경우 중에서 K - dp[n - 1][m]번 째의 경우이기 때문에
         * findAnswer(n, m - 1)를 진행하기 전에 K에서 dp[n - 1][m]를 뺀 후에 진행한다.
         */
        else {
            K -= dp[n - 1][m];
            answer.append('z');
            findAnswer(n, m - 1);
        }
    }
}