[백준 1256] 사전(Java)

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

이 문제는 dp를 이용하여 풀 수 있습니다. 이 문제의 경우 크게 2가지 부분에서 아이디어가 필요합니다.

1. dp 점화식은 어떻게 세울 것인가
2. dp 점화식과 문자열과의 상관관계는 어떤 식으로 처리해야 하는가

우선 1번의 경우 dp 점화식을 문자열의 개수로 설정합니다. 즉 dp[n][m] : a가 n개이고, z가 m개인 문자열의 개수로 설정합니다. 그 이유는 문제에서 K의 범위를 초과했을 경우 -1을 출력해야 하기 때문에 문자열 개수에 대한 정보를 가지고 있어야 하며, 뒤이어 설명드릴 2번 방식을 문자열 개수에 대한 정보로 처리할 수 있기 때문입니다.

2번의 경우는 케이스를 나눠서 확인할 수 있습니다. 만약 a 또는 z의 개수가 0일 경우 반대되는 문자를 끝까지 추가하면 됩니다. 하지만 둘 다 0이 아닌 경우는 k과 직전 dp값을 비교하는 방식으로 진행합니다.

만약 a가 하나 없는 dp, 즉 dp[n-1][m]보다 k가 작을 때를 생각해봅시다. dp[n-1][m]의 경우 a가 n-1개, z가 m개 존재하는 문자열의 개수를 의미하고 k는 순서를 의미합니다. 따라서 dp[n-1][m]의 값보다 k가 작을 경우는 앞쪽에서 수를 선택해서 문자열을 추가하는 것이므로 정렬된 값을 출력하기 때문에 a가 추가되어야 합니다. 마찬가지로 k가 더 크다면 z를 출력합니다.

이 때 z를 추가할 경우, 즉 dp[n-1][m]이 k보다 작을 경우 다음 수를 추가할 때 그 이후의 dp값들은 모두 k보다 작게 된다는 문제점이 있습니다. 이는 k값을 해당 값만큼 빼는 방식으로 k값의 크기를 조정해주면 뒤의 수들을 정상적으로 추가할 수 있습니다.

다음은 코드입니다.

import java.util.*;
import java.io.*;

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

    static int init(int n, int m){
        // dp[n][m] : a가 n개이고, z가 m개인 문자열의 개수

        // 초기값 세팅
        // 두 값 중 어느 하나라도 0이면 개수는 1개밖에 만들지 못함
        if(n==0 || m==0){
            dp[n][m] = 1;
            return dp[n][m];
        }

        // dp에 값이 없다면 점화식으로 : dp[n-1][m] + dp[n][m-1]
        // dp[n][m]의 개수는 a가 하나 없는 문자열의 개수와 z가 하나 없는 문자열의 개수의 합과 같음
        else if(dp[n][m]==0){
            // 여기서 K값이 10억 이하이므로 10억 초과인 값이 점화식으로 나오게 된다면 -1로 처리해야 할 부분까지 처리하는 것이므로 10억으로 처리
            dp[n][m] = Math.min(init(n-1,m) + init(n,m-1), 1000000001);
            return dp[n][m];
        }

        // 값이 존재한다면 해당값 출력
        else return dp[n][m];
    }

    static void setString(int n, int m, int k){
        // 만약 a의 개수가 0일 경우 z만 이어서 추가
        if(n==0){
            for(int i=0;i<m;i++) sb.append("z");
            return;
        }

        // 만약 z의 개수가 0일 경우 a만 이어서 추가
        if(m==0){
            for(int i=0;i<n;i++) sb.append("a");
            return;
        }

        // 둘 다 살아있을 경우 맨 앞에서부터 문자열 추가
        // 바로 직전 dp의 값과 k값과 비교했을 때
        // 만약 a가 하나 없는 dp값보다 k가 작다면
        // k의 경우 순서를 의미하기 때문에 추가해야 할 문자는 a가 됨
        // 반대로 k가 크다면 z를 추가하는 식으로 진행
        // 이 때 z를 추가할 경우 k값에서 직전 dp값을 빼주어 다음 문자열을 추가할 때의 순서값을 보정
        if(k > dp[n-1][m]){
            sb.append("z");
            setString(n,m-1,k-dp[n-1][m]);
        }

        else{
            sb.append("a");
            setString(n-1,m,k);
        }
    }

    public static void main(String[] args) throws Exception{
        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 배열 값 추가
        init(N,M);

        // K가 문자열 개수보다 클 경우 -1 출력
        if(dp[N][M] < K) System.out.println(-1);

        // 아닐 경우 : 문자열 생성
        else{
            setString(N,M,K);
            System.out.println(sb);
        }

    }
}