167. 사전

백준

1. Python

참고

import sys
input = sys.stdin.readline
 
n, m, k = map(int, input().split())
# n, m개 대신, 최댓값 101로도 선언 가능
arr = [[1]*(m + 1) for _ in range(n + 1)] #a or z 로만 이루어진 단어는 1개뿐
 
for i in range(1, n+1):
    for j in range(1, m+1):
        arr[i][j] = arr[i-1][j] + arr[i][j-1] #a를 하나 뺀 단어, z를 하나 뺀 단어
 
if arr[n][m] < k:
    print(-1)
else:
    result = ""
    while True:
        if n == 0 or m == 0:
            result += "z"*m
            result += "a"*n
            break
 		
        #앞에서부터 알파벳 확인 
        flag = arr[n-1][m] 
        if k <= flag:
            result += "a"
            n -= 1
        else:
            result += "z"
            m -= 1
            k -= flag
    print(result)

P를 이용하여 a와 z로 만들수 있는 총 단어 개수를 구한다.

• 만들 수 있는 단어 개수를 저장하는 arr[a의 개수][z의 개수]를 생성한다.

• a로만 이루어진 단어와 z로만 이루어진 단어는 1개뿐이므로 arr[?][1] = arr[1][?] = 1이다.

• DP를 통해 arr[i][j]는 a를 하나 뺀 단어(arr[i-1][j])와 z를 하나 뺀 단어(arr[i][j-1])를 합치면 된다.

• K가 더크다면 -1을 출력한다.

• 제일 앞 알파벳이 a라고 했을 때 가질 수 있는 단어 개수는 arr[N-1][M] 개이다.

• K가 arr[N-1][M]보다 작거나 같다면 앞 알파벳이 a이고, 크다면 z이다.
  이런식으로 앞에서부터 알파벳을 정해 결과를 출력해준다.
  

2. Java

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

public class Main {
    private static int N, M, K;
    private static int[][] cache;
    private static char[] answer;
    private static final int INF = 1000000010;

    public static void main(String[] args) throws Exception {       
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        cache = new int[101][101];
        for (int i = 0 ; i <= 100 ; i++) {
            for (int j = 0 ; j <= 100 ; j++) {
                cache[i][j] = -1;
            }
        }
        answer = new char[N + M];

        if (getAZ(N, M) < K) {
            System.out.println(-1);
            return;
        }

        // to-do
        // 가장 앞에 있는 문자열부터 채워 나간다
        int countA = N, countZ = M; // 앞으로 사용할 수 있는 문자

        for (int i = 0 ; i < N + M ; i++) {
            // i 번째 문자열이 a라면.....
            if (countA > 0) {
                int tmp = getAZ(countA - 1, countZ);
                if (tmp < K) {
                    answer[i] = 'z';
                    K -= tmp;
                    countZ--;
                }
                else {
                    answer[i] = 'a';
                    countA--;
                }
            }
            else {
                answer[i] = 'z';
            }
        }
        System.out.println(new String(answer));
    }

    public static int getAZ(int a, int z) {     
        if (a == 0 || z == 0) {
            return 1;
        }
        if (cache[a][z] != -1) {
            return cache[a][z];
        }
        cache[a][z] = getAZ(a - 1, z) + getAZ(a, z - 1);
        if (cache[a][z] >= INF) {
            cache[a][z] = INF;
        }
        return cache[a][z];
    }
}