[백준 JAVA 1256] 사전

 

다이나믹 프로그래밍 문제

 

처음에는 Factorial을 이용해 해당 순번 string을 구하려 했으나, 연산량이 불필요하게 많아져 포기

 

dp기법을 이용해 n개의a와 m개의 z로 만들 수 있는 string의 갯수를 기록하여 연산량을 줄임

 

dp점화식은 dp[n][m] = dp[n-1][m]+dp[n][m-1]

 

string을 찾는 방법은 k가 n,m으로 가능한 갯수보다 크면 z를 붙이고 k-chekc(n,m)을 통해 순번을 줄여주고 z의개수 감소(m-1)

아닐경우 a를 붙여주고 a의 갯수감소

 

계속 위와같은방법으로 재귀를하다 끝낸다.

 

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

class Main {
    static int[][] dp = new int[101][101];
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        if (check(N, M) < K) {
            System.out.println("-1");

        }else{
            find(N, M, K);
            System.out.println(sb.toString());
        }

    }

    public static int check(int n, int m) {
        if (n == 0 || m == 0) {
            return 1;
        }
        if (dp[n][m] != 0) return dp[n][m];

        return dp[n][m] = Integer.min(check(n - 1, m) + check(n, m - 1), 1000000001);
    }

    public static void find(int n, int m, int k) {
        if (n == 0) {
            for (int i = 0; i < m; i++) {
                sb.append("z");
            }
            return;
        }
        if (m == 0) {
            for (int i = 0; i < n; i++) {
                sb.append("a");
            }
            return;
        }
        int check = check(n - 1, m);
        if (k > check) {
            sb.append("z");
            find(n, m - 1, k - check);
        } else {
            sb.append("a");
            find(n - 1, m, k);
        }
    }
}