[백준/Java] 1256 사전

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

문제 요약

사전의 모든 문자열은 N개의 a와 M개의 z로 구성된다.
사전이므로 당연히 문자열은 알파벳 순서로 수록되어 있다.
N과 M이 주어질 때, K번째 문자열을 구하여라.
만약 사전이 K보다 작다면 -1을 출력한다.

문자열을 구성하는 a의 개수 N은 최대 100이다.
문자열을 구성하는 z의 개수 M은 최대 100이다.
사전에서 찾을 문자열의 순서 K는 최대 10억이다.

---

문제 접근

가능한 모든 문자열을 찾고 K번째 문자열을 찾을 수 있으면 좋겠지만, M과 N이 각각 100이라고 하면 가능한 문자열의 개수가 ${}_{200}C_{100}$이고, 이는 굉장히 큰 수이므로 시간적으로도 공간적으로도 불가능하다.

그러면 K번째까지만 찾으면 되지 않을까 할 수 있지만, K가 최대 10억이므로 하나하나 찾는 시간복잡도인 $O(K)$도 불가능한 상황이다.

이 문제를 해결하기 위해서는 조합론과 DP를 사용해야 한다.
먼저 조합론에서 ${}_{n}C_{r}={}_{n-1}C_{r-1}+{}_{n-1}C_{r}$임을 이용한다.
이 공식을 앞에서부터 문자를 하나씩 추가하며 a를 추가할 지, 아니면 z를 추가할 지 판단하는데 사용한다.

문제 상황에서 더 추가해야 할 a의 개수를 n, 더 추가해야 할 z의 개수를 m이라고 하면 ${}_{n+m}C_{m}={}_{n+m-1}C_{m-1}+{}_{n+m-1}C_{m}$이 성립한다.
${}_{n+m-1}C_{m-1}$은 z를 추가한 이후 가능한 문자열 개수를 의미하며, ${}_{n+m-1}C_{m}$은 a를 추가한 이후 가능한 문자열 개수를 의미한다.
이때 a를 추가하는 것이 사전 상 더 우선이기 때문에 ${}_{n+m-1}C_{m}$를 기준으로 추가 여부를 판단한다.

1. 만약 ${}_{n+m-1}C_{m}$가 K보다 크거나 같다면 a를 추가한 다음의 문자열 조합에서 K번째 문자열을 찾을 수 있다는 것이기 때문에 a를 추가한다.
2. 그렇지않고 ${}_{n+m-1}C_{m}$가 K보다 작다면 a를 추가한 문자열 조합 개수를 넘어서 z를 추가한 경우에서 K번째 문자열을 찾을 수 있다는 것이기 때문에 z를 추가한다.
   다만 이때는 K의 상대적인 위치가 변하기 때문에 K에서 ${}_{n+m-1}C_{m}$ 값을 빼어 보정해야 한다.

이렇게 조합론 공식이 꾸준히 사용되는데, 이를 사용할 때마다 계산하는 것도 큰 비용이 든다.
그래서 이러한 값들을 미리 계산해놓고 기록해야 하며, DP가 여기서 사용된다고 할 수 있다.
조합론 공식을 이용해 파스칼의 삼각형을 다 채운 후, 위의 방식대로 K번째 문자열을 찾을 때 이를 가져다 사용한다.

이를 구현한 코드는 다음과 같다.

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

public class Main {
	
	static final int MAX_VALUE = 1000000001;
	
    static int N, M, K;
    static int[][] triangle;
    
    public static void main(String[] args) throws IOException {
    	
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        // 입력 받기
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        
        // 파스칼의 삼각형
        // 인덱스 0도 사용하지만, 인덱스 접근은 해당 값으로 바로 하면 된다.
        triangle = new int[N+M+1][N+M+1];
        
        // 경우의 수 값이 K를 넘어서는 경우를 처리하기 위해 MAX_VALUE를 사용한다.
        // MAX_VALUE의 값은 10억+1이고, int의 한계는 21억이므로 int를 넘지 않는다.
        
        // 조합의 특성을 이용해 파스칼의 삼각형을 채운다.
        // n C r = (n-1) C (r-1) + (n-1) C r (r == 0 || r == n이면 그냥 1)
        triangle[0][0] = 1;
        for (int i = 1; i < N+M+1; i++) {
        	triangle[i][0] = 1; // 0개를 선택하는 경우는 모두 1
        	// 0개에서 j개를 선택하는 것은 모두 0으로 초기화가 되어 있다.
        	for (int j = 1; j <= i; j++) {
        		triangle[i][j] = Math.min(triangle[i-1][j-1] + triangle[i-1][j], MAX_VALUE);
        	}
        }

        // 문자열의 개수가 K보다 작으면 -1을 출력
        if (K > triangle[N+M][M]) {
        	System.out.println(-1);
        }
        // a를 추가할 지, z를 추가할 지 결정
        // a를 하나 줄인 (N+M-1) C (M) 보다 K가 작거나 같다면 a를 추가하여 진행하고,
        // K가 더 크다면 z를 추가하여 진행한다(이때는 K를 두 값의 차로 갱신).
        else {
        	while (true) {
        		if (K <= triangle[N+M-1][M]) {
            		sb.append("a");
            		N--;
            	}
            	else {
            		sb.append("z");
            		K -= triangle[N+M-1][M];
            		M--;
            	}
            	
            	// 만약 a나 z를 모두 사용했다면 남은 것들을 다 뒤에 붙임
            	if (N == 0) {
            		for (int i = 0; i < M; i++) {
            			sb.append("z");
            		}
            		break;
            	}
            	if (M == 0) {
            		for (int i = 0; i < N; i++) {
            			sb.append("a");
            		}
            		break;
            	}
        	}        	

        	// 정답 출력
        	System.out.println(sb);
        }
    }
}

---

회고

이 문제도 내 생각만으로 푼 문제는 아니다. 조합론은 너무 헷갈린다.

틀렸던 이유
DP를 사용하지 않고 M개의 z 사이에 N개의 a를 끼어넣는 재귀를 이용해 문제를 해결하려고 했는데, 이게 결국 $O(K)$가 되는 거라서 시간초과가 났다.