[JAVA][BOJ 1256] 조합: 사전 찾기

문제링크

문제 파악

N개의 'a', M개의 'z'로 사전을 만들었다. 알파벳 순서로 수록된 사전에서 K번째 문자열 구하기

• 사전에 있는 수가 K보다 작으면 -1 반환

N개의 'a', M개의 'z', K번째 문자열

• 1 ≤ N, M ≤ 100
• 1 ≤ K ≤ 1,000,000,000

접근 방법

각 자리 수까지 만들 수 있는 문자열 개수 < K, K랑 가장 근접한 개수에서 노가다로 푸는게 생각이 났다.

중복한 문자를 가지기 때문에 만들 수 있는 문자열의 개수는 N+M개 중 N개 또는 M개를 택하는 것과 같다.

순열과 똑같이 전체 중에서 칸막이를 넣는다고 생각하면 된다.

그리고 순열의 nCr = n-1 C r-1 + n-1 C r 을 이용하면 DP가 된다.   

DP

부문 문제가 해결된 상황에서 마지막 데이터의 선택 여부에 따른 경우의 수 계산하는 것이다.

DP[5][3] = DP[4][2] + DP[4][3]

• 5개 중 4개를 이미 선택 완료한 데이터라 가정
• 5개 중 3개를 선택 = 4개 중 2개 선택 + 4개 중 3개 선택

DP[n+m][n] = T = 남아있는 문자들로 만들 수 있는 경우의 수 

T >= K: 현재 자리 문자를 a로 선택
T < K: 현재 자리 문자를 z로 선택하고, K = K - T 로 업데이트

• K = K - T 로 업데이트 하는 이유는, 만약 DP[][] = 3이고, K(4)번째일 때, a를 놓았을 때 경우의 수가 3개 생긴다는 뜻이므로 a로 놓았을 경우 3개를 K에서 빼주고 z로 놓는다.   

코드 구현

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();

        // DP 테이블 초기화
        int[][] DP = new int[202][202];
        for (int i = 0; i <= 200; i++) {
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) DP[i][j] = 1;
                else {
                    DP[i][j] = DP[i - 1][j - 1] + DP[i - 1][j];
                    // k보다 큰 범위는 볼 필요없기 때문에 범위의 최댓값 입력
                    if (DP[i][j] > 1000000000) DP[i][j] = 1000000001;
                }
            }
        }

        // 주어진 K가 만들 수 있는 조합 수보다 크면 불가능
        if (DP[n + m][m] < k) {
            System.out.println("-1");
            return;
        }

        // 결과를 담을 StringBuilder
        StringBuilder sb = new StringBuilder();

        // n, m이 0이 될 때까지 반복
        while (!(n == 0 && m == 0)) {
            if (n > 0 && DP[n - 1 + m][m] >= k) {
                sb.append("a");
                n--;
            } else {
                if (n > 0) k -= DP[n - 1 + m][m];
                sb.append("z");
                m--;
            }
        }

        // 최종 결과 출력
        System.out.println(sb.toString());
    }
}

배우게 된 점

DP가 부분 문제의 마지막 순간을 선택한다는 걸 순열의 n-1Cr-1 + n-1Cr로 이어서 생각할 수도 있다는 것을 배웠다 .

질문