[Java] BOJ1256, 백준 - 사전

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

1256번: 사전

n, m, k가 주어졌을 때 가능한 순서의 총 경우의 수는 전체 경우의 수를 중복되는 a와 z의 수로 나눈 (n+m)!/(n!m!)이다.
이를 바탕으로 n+m자리의 문자열을 만들 때, dp방식으로 접근.
예를 들어서
첫 번째 문자열의 경우의 수는 총 (n+m)!/(n!m!)
첫 번째 문자가 a였다고 가정했을 때, 그 다음은
a + (n+m-1)!/((n-1)!m!)
두 번째 문자도 a라고 가정하면
aa + (n+m-2)!/((n-2)!m!)
와 같은 형식으로 진행된다.

그렇다면 문자가 a인지 z인지는 어떻게 판단하는가?
n+m자리 문자열을 만드는 경우는
a+ (n+m-1)!/((n-1)!m!)의 경우와 z + (n+m-1)!/(n!(m-1)!)의 경우를 합친 경우일 것이다.
문자열이 사전 순으로 만들어지기 때문에 (n+m)!/(n!m!)중에서 (n+m-1)!/((n-1)!m!)번째 수 까지의 문자열은 a가 되고 나머지는 z가 된다.
즉, 점화식은 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]이고
문자열은 k와 dp[n - 1][m]를 비교해주면 a인지 z인지 알 수 있게 된다.

*점화식에 대한 간단한 증명

 

*소스코드

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

public class BJ1256 {
    private static int[][] dp;
    private static int n, m;

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

        n = parse(st.nextToken()); // a개수
        m = parse(st.nextToken()); // z개수
        int k = parse(st.nextToken());

        fillArr();

        if (k > dp[n][m]) {
            System.out.println(-1);
            return;
        }

        StringBuilder sb = new StringBuilder();
        // k번째 수 구하기
        while (n > 0 || m > 0) {
            int a = (n <= 0) ? 0 : dp[n - 1][m];

            if (k <= a) {
                // a를 이어붙이면 됨
                n--;
                sb.append("a");
            } else {
                m--;
                k -= a;
                sb.append("z");
            }
        }
        System.out.println(sb.toString());
    }

    private static void fillArr() {
        dp = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }

        for (int i = 1; i <= m; i++) {
            dp[0][i] = 1;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = Math.min(dp[i - 1][j] + dp[i][j - 1], 1000000001);
            }
        }
    }

    private static int parse(String s) {
        return Integer.parseInt(s);
    }
}