[BaekJoon] 1256 사전 (Java)

1.  문제 링크

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

2.  문제

요약

• 동호와 규완이는 특별한 문자열로 이루어진 사전을 만드려고 하는데 사전에 수록되어 있는 모든 문자열은 N개의 "a"와 M개의 "z"로 이루어져 있으며 사전에는 알파벳 순서대로 수록되어 있습니다.
• 동호는 규완이가 완성한 사전에서 문자열 하나를 찾으려고 합니다.
• N과 M이 주어졌을 때, 규완이의 사전에서 K번째 문자열이 무엇인지 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 100보다 작거나 같은 정수 N, M과 1보다 크거나 같고 1,000,000,000보다 작거나 같은 정수 K가 주어집니다.
• 출력: 첫 번째 줄에 규완이의 사전에서 K번째 문자열을 출력합니다. 만약 규완이의 사전에 수록되어 있는 문자열의 개수가 K보다 작으면 -1을 출력합니다.

3.  소스코드

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

public class Main {
    static final int SIZE = 100;
    static StringBuilder sb = new StringBuilder();
    static int N, M, K;
    static double[][] dp;

    static void input() {
        Reader scanner = new Reader();

        N = scanner.nextInt();
        M = scanner.nextInt();
        K = scanner.nextInt();
    }

    static void solution() {
        dp = new double[SIZE + 1][SIZE + 1];

        if(checkNum(N, M) < K) {
            System.out.println(-1);
            return;
        }

        makeString(N, M, (double)K);
        System.out.println(sb);
    }

    static double checkNum(int aNum, int zNum) {
        if(aNum == 0 || zNum == 0)
            return 1;

        if(dp[aNum][zNum] != 0)
            return dp[aNum][zNum];

        return dp[aNum][zNum] = Double.min(checkNum(aNum - 1, zNum) + checkNum(aNum, zNum - 1), 1000000001);
    }

    static void makeString(int aNum, int zNum, double target) {
        if(aNum == 0) {
            for(int idx = 0; idx < zNum; idx++)
                sb.append('z');

            return;
        }

        if(zNum == 0) {
            for(int idx = 0; idx < aNum; idx++)
                sb.append('a');

            return;
        }

        double totalNum = checkNum(aNum - 1, zNum);

        if(target > totalNum) {
            sb.append('z');
            makeString(aNum, zNum - 1, target - totalNum);
        } else {
            sb.append('a');
            makeString(aNum - 1, zNum, target);
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}