백준 1256번 - 사전

문제

백준 1256번 - 사전

---

아이디어

모든 문자열을 직접 재귀로 만들어보는 방법은 (N + M)!개의 문자열을 만들어내야 해서 메모리 초과가 발생한다.

DP와 분할 정복 알고리즘 조합으로 K번째 문자열을 한 문자씩 구해나간다.

1. DP 배열 초기화

dp = new long[n + m + 1][n + m + 1];

for (int i = 0; i <= n + m; i++) {

    dp[i][0] = dp[i][i] = 1;
    
    for (int j = 1; j < i; j++) {
        dp[i][j] = Math.min(dp[i - 1][j] + dp[i - 1][j - 1], 1_000_000_001); //오버플로우 방지
    }
}

• dp[i][j]는 i개 중 j개를 고르는 경우의 수를 의미한다. 문자열을 처음부터 하나씩 만드는 대신 이 배열의 값을 이용해 구한다.

2. 결과 출력

if (k > dp[n + m][n]) {
    System.out.println(-1);
    return;
}

System.out.println(solve(n, m, k));

• dp[n + m][n]은 전체 n + m 길이의 문자열 중 n개를 고른 경우의 수, 즉 가능한 전체 문자열의 수를 의미한다.
• 만약 k가 이 수보다 크면 찾을 수 없음을 의미한다. (같은 원리로 dp[n + m][n] 대신 dp[n + m][m]을 조건으로 해도 된다.)
• 그렇지 않으면 solve 메서드를 호출한다.

3. solve 메서드

private static String solve(int n, int m, long k) {

    //N개 또는 M개 문자를 다 소진했을 경우, 남은 문자로 뒤를 채운다.
    if (n == 0) return "z".repeat(m);
    if (m == 0) return "a".repeat(n);
    
    //현재 "a"를 선택했을 때 만들 수 있는 문자열의 개수
    long a = dp[n + m - 1][n - 1];
    
    if (k <= a) {
        return "a" + solve(n - 1, m, k);
    } else {
        return "z" + solve(n, m - 1, k - a);
    }
}

• 문자열 순서는 사전순이기 때문에 일단 현재 자리에 a를 놓았을 때 남은 문자들로 만들 수 있는 경우의 수를 확인한다.(변수 a)
• 만약 k <= a면, 현재 위치에 a를 둘 수 있음을 의미하고, 그렇지 않으면 z를 두고 k를 조정해준다.

---

예상 시간 복잡도

• 예상 시간 복잡도 : O(NM)

---

코드 구현 - 자바

package Baekjoon.dp;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/**
 * <a href = "https://www.acmicpc.net/problem/1256">백준 1256번 - DP : 사전</a>
 * <br>
 * <a href = "">velog</a>
 * @since 2025-01-06
 */
public class BJ_1256 {

    static long[][] dp;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        long k = Long.parseLong(st.nextToken());

        dp = new long[n + m + 1][n + m + 1];

        for (int i = 0; i <= n + m; i++) {
            dp[i][0] = dp[i][i] = 1;
            for (int j = 1; j < i; j++) {
                dp[i][j] = Math.min(dp[i - 1][j] + dp[i - 1][j - 1], 1_000_000_001);
            }
        }

        if (k > dp[n + m][n]) {
            System.out.println(-1);
            return;
        }

        System.out.println(solve(n, m, k));
    }

    private static String solve(int n, int m, long k) {

        //N개 또는 M개 문자를 다 소진했을 경우, 남은 문자로 뒤를 채운다.
        if (n == 0) return "z".repeat(m);
        if (m == 0) return "a".repeat(n);

        //현재 "a"를 선택했을 때 만들 수 있는 문자열의 개수
        long a = dp[n + m - 1][n - 1];

        if (k <= a) {
            return "a" + solve(n - 1, m, k);
        } else {
            return "z" + solve(n, m - 1, k - a);
        }
    }
}

코드 구현 - 파이썬

n, m, k = map(int, input().split())
dp = [[0] * (n + m + 1) for _ in range(n + m + 1)]


def solve(n, m, k):
    if n == 0:
        return 'z' * m
    if m == 0:
        return 'a' * n

    a = dp[n + m - 1][n - 1]

    if k <= a:
        return 'a' + solve(n - 1, m, k)
    else:
        return 'z' + solve(n, m - 1, k - a)


for i in range(n + m + 1):
    dp[i][0] = dp[i][i] = 1
    for j in range(1, i):
        dp[i][j] = min(dp[i - 1][j] + dp[i - 1][j - 1], 1_000_000_001)

if k > dp[n + m][n]:
    print(-1)
else:
    print(solve(n, m, k))