[백준] 1256번 사전 (JAVA)

문제

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

1256번: 사전

 

설명

사전에 수록되어 있는 모든 문자열은 N개의 "a"와 M개의 "z"로 이루어져 있고 알파벳 순서대로 수록되어 있다.
사전에서 K번째 문자열이 무엇인지 구해야 한다.

사전에 수록되어 있는 문자열의 갯수는 \({}_{N + M}\mathrm{C}_{M}\) 이다.

그 값이 K보다 작다면 -1을 출력하고 그렇지 않다면 query를 진행해 K번째 문자열을 찾는다.

if (combination(N + M, M) < K)
    System.out.println(-1);
else {
    query(N, M ,K);
    System.out.println(answer);
}

combination 함수에서는 조합 공식과 파스칼의 삼각형을 이용한다.

\({}_{n}\mathrm{C}_{0}\) 과 \({}_{n}\mathrm{C}_{n}\) 은 모두 1이고 이미 구한 값은 계산과정 없이 바로 그 값을 리턴한다.

그 외의 값은 파스칼의 삼각형을 통해 pascal[][] 배열을 채워간다.

int combination(int total, int choose) {
    if (choose == 0 || total == choose)
        return 1;
    else if (pascal[total][choose] != 0) {
        return pascal[total][choose];
    }
    else {
        return pascal[total][choose] = (int) Math.min(1e9, combination(total - 1, choose) + combination(total - 1, choose - 1));
    }
}

해당 순번의 값을 찾기 위한 query 함수에서는 문자열을 이룰 문자를 하나씩 판단한다. 

문자열은 반드시 n개의 'a'와 m개의 'z'로 이루어져야 하므로 해당 자리를 제외한 나머지 자리에 올 수 있는 경우의 수를 의미하는 limit을 구한다.

limit보다 k가 작거나 같다면 문자열에 'a'를 추가하고, 이제 문자열에는 (n - 1)개의 'a'가 필요하므로 이를 반영해 query를 진행한다.

그렇지 않다면 'z'를 추가하고, 이제 문자열에는 (m - 1)개의 'z'가 필요하고 limit 뒤에서부터 순서를 찾아야 하므로 이를 반영해 query를 진행한다.

void query(int n, int m, int k) {
    if (n + m == 0) {
        return;
    }
    else if (n == 0) {
        answer.append("z");
        query(n, m - 1, k);
    }
    else if (m == 0) {
        answer.append("a");
        query(n - 1, m, k);
    }
    else {
        int limit = combination(n + m - 1, m);
        if (limit >= k) {
            answer.append("a");
            query(n - 1, m, k);
        }
        else {
            answer.append("z");
            query(n, m - 1, k - limit);
        }
    }
}

 

전체 코드

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

public class Main {

    static int N, M, K;
    static int[][] pascal = new int[201][201];
    static StringBuilder answer = new StringBuilder();

    static int combination(int total, int choose) {
        if (choose == 0 || total == choose)
            return 1;
        else if (pascal[total][choose] != 0) {
            return pascal[total][choose];
        }
        else {
            return pascal[total][choose] = (int) Math.min(1e9, combination(total - 1, choose) + combination(total - 1, choose - 1));
        }
    }

    static void query(int n, int m, int k) {
        if (n + m == 0) {
            return;
        }
        else if (n == 0) {
            answer.append("z");
            query(n, m - 1, k);
        }
        else if (m == 0) {
            answer.append("a");
            query(n - 1, m, k);
        }
        else {
            int limit = combination(n + m - 1, m);
            if (limit >= k) {
                answer.append("a");
                query(n - 1, m, k);
            }
            else {
                answer.append("z");
                query(n, m - 1, k - limit);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        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());

        if (combination(N + M, M) < K)
            System.out.println(-1);
        else {
           query(N, M ,K);
           System.out.println(answer);
        }
    }
}