[백준 1256] 사전 (JAVA)

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

1256번: 사전

---

a 와 z 로만 구성된 문자열을 만들 수 있는 경우의 수를 구한다는 것은 

 

n+m 개 중에서 n 개(혹은 m 개) 를 선택하는 경우의 수와 같다. (a 는 n 개, z 는 m 개)

 

각각의 문자열이 사전식 배열로 이루어져있다고 가정하므로,

 

k 번째 문자열을 알아내기 위해서는, n+m 개의 문자 중에서 n 개 (혹은 m개) 를 선택하는 경우의 수를 먼저 구해야 한다.

 

그리고 나서, a 를 선택했다고 가정하고 나머지 문자들로 만들 수 있는 경우의 수가 k 보다 크거나 같다면 해당 자리에 알파벳 a 를 선택하였을 때 만들 수 있는 문자열의 개수가 k 개 보다 크다는 것이고 이는 곧 k 번째 문자열이 존재한다는 것이므로 a 를 선택한다.

 

만약에 a 를 선택한다고 가정했을 때 나머지 문자들로 만들 수 있는 경우의 수가 k 보다 작다면, a 를 선택하면 나머지 문자열들의 조합으로 만들 수 있는 문자열의 개수가 k 개 보다 작으므로 k 번째 문자열이 존재하지 않는다는 의미이므로 z 를 선택해야 한다는 것이다. 그러한 경우에는 z 를 선택하고, 경우의 수 k 를 업데이트 해준다.

 

⭐ 유의해야 할 점은, m+n 개의 문자 중에서 n(혹은 m)  개를 선택하는 경우의 수가 long 의 범위를 뛰어넘어서 overflow 가 발생하는 경우를 고려해주어야 한다. k 의 제한이 10^10 이므로,  조합 테이블을 계산할 때, k 값 보다 크다면 그냥 10^10+1 정도로 저장해주어야 한다는 것을 생각해내야 한다.

import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        Scanner sc =new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = sc.nextInt();
        int m = sc.nextInt();
        long k = sc.nextLong();

        long [][] dp = new long[202][202];
        // 1. 조합 테이블 구성하기
        for(int i = 0; i <= 200; i++){
            dp[i][1] = i; // ex) 3C1 = 3
            dp[i][0] = 1; // ex) 3C0 = 1
            dp[i][i] = 1; // ex) 3C3 = 1
        }
        for(int i = 1 ; i <= 200; i++){
            for(int j = 1; j<=i; j++){
                // i 개에서 j 개를 뽑을 때 j 가 i 보다 클 수는 없음.
                dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
                // 예를 들어 5개 중 3 개를 선택해야 하는 경우의 수를 구한다면
                // 이는 4개 중에서 2개를 선택하고 마지막에 한번 더 선택하는 경우의 수와
                // 4개 중에서 3개를 선택하고 마지막에 선택을 하지 않은 경우의 수의 합과 같음.
                if(dp[i][j] > 1000000000)
                    dp[i][j] = 1000000001; // 오버 플로우를 방지하기 위해 k 값의 최대로 제한함.
            }
        }
        // 2. 예외 처리
        if(dp[m+n][m] < k){
            // 사전은 a 와 z 로만 이루어져 있으므로 (m+n) 개 중에서 m 개 혹은 n 개를 선택하는
            // 경우의 수 만큼의 문자가 존재하기 때문에,
            // m+n 개 중에서 m 개를 선택하는 경우의 수가 k 개 보다 작다면 
            // k 번째 문자열이 존재하지 않는 경우이다. 그러한 경우에는 -1 을 출력
            System.out.println("-1");
            return; // 메인 메서드 종료
        }
        // 3. 주어진 문자열 만들기
        while(!(n==0&&m==0)){ // 'a' 와 'z' 를 다 사용할 때 까지 반복
            // 만약 a 를 선택했다면?
            if(dp[m+n-1][m] >= k){ // a 를 선택했다고 치고 나머지 문자열의 경우의수와 k 를 비교
                bw.append("a");
                n--; // a 를 하나 사용한 것이니까 개수 감소
            } else { // 근데 k 가 더 크다면, a 를 선택하면 k 번째 문자열을 만들 수 없어서 안된다는 것임
                // 그러니까 z 를 선택해야 함.
                bw.append("z");
                k = k - dp[m+n-1][m]; // z 를 선택한 것으로 경우의 수를 업데이트 함
                m--; // z 를 하나 사용한 것이니까 개수 감소
            }
        }
        bw.flush();
        bw.close();
    }
}