백준 1256 - 사전

1256번: 사전 (acmicpc.net)

1256번: 사전

 

문제

동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 김진영 조교는 동호와 규완이에게 특별 과제를 주었다. 특별 과제는 특별한 문자열로 이루어 진 사전을 만드는 것이다. 사전에 수록되어 있는 모든 문자열은 N개의 "a"와 M개의 "z"로 이루어져 있다. 그리고 다른 문자는 없다. 사전에는 알파벳 순서대로 수록되어 있다.

규완이는 사전을 완성했지만, 동호는 사전을 완성하지 못했다. 동호는 자신의 과제를 끝내기 위해서 규완이의 사전을 몰래 참조하기로 했다. 동호는 규완이가 자리를 비운 사이에 몰래 사전을 보려고 하기 때문에, 문자열 하나만 찾을 여유밖에 없다.

N과 M이 주어졌을 때, 규완이의 사전에서 K번째 문자열이 무엇인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 N, M, K가 순서대로 주어진다.

출력

첫째 줄에 규완이의 사전에서 K번째 문자열을 출력한다. 만약 규완이의 사전에 수록되어 있는 문자열의 개수가 K보다 작으면 -1을 출력한다.

 

 

문제는 a, z로만 이루어진 특별한 문자열 사전에서 K번째 문자열을 찾는 알고리즘을 구하는 것이다. 솔직히 dp 문제를 풀고 싶어서 백준 dp 문제들 중에 문제를 찾았기 때문에 dp로 해결할 수 있었지, 처음 봤으면 절대 dp를 생각하지 못했을 것 같은 문제였다.

 

※ 알고리즘

1. 첫 번째 'a'와 첫 번째 'z'만 있는 경우는 1가지씩만 존재하므로, dp 테이블을 1로 초기화한다.

2. dp 테이블을 이용해서 'a'와 'z'로 만들 수 있는 모든 문자열의 개수를 저장한다.

-> dp[i][j] = dp[i-1][j] + dp[i][j-1]이 dp 테이블 알고리즘의 핵심인데, 이 부분을 따로 살펴보자.

dp[i-1][j] : 'a'가 하나 적고, 'z'의 개수가 같을 때 생성할 수 있는 문자열의 개수(다음 문자로 'a'를 선택하는 경우의 수)

dp[i][j-1] : 'a'의 개수는 같고, 'z'가 하나 적을 때 생성할 수 있는 문자열의 개수(다음 문자로 'z'를 선택하는 경우의 수)

 

dp[i][j] 를 위 두개의 dp테이블로 나타내면, 'a'를 다음 문자로 선택하는 경우와 'z'를 다음 문자로 선택하는 경우의 합이므로, 'a'가 i개, 'z'가 j개 있을 때 생성할 수 있는 모든 문자열의 개수를 의미한다.

 

3. dp 테이블을 이용하여 k번째 문자열을 실제로 구성한다.

-> 'a' 또는 'z'가 더 이상 없을 경우에는 남은 문자를 단순히 붙여서 구성

-> k가 현재 위치에서 'a'로 시작하는 문자열 갯수보다 작거나 같으면, 문자열은 'a로 시작하고 재귀적으로 그 다음 문자를 찾는다.

-> 그 외의 경우에서는 'z'로 시작하므로, k에서 'a'로 시작하는 문자열의 개수를 빼고 재귀 호출을 한다.

 

4. 만약 k가 dp 테이블에 저장된 최대 문자열 수보다 크면, 해당하는 문자열이 없으므로 -1을 반환한다.

그렇지 않다면 k 번째 문자열을 구성해준다.

 

import sys
input = sys.stdin.readline

n, m, k = map(int, input().split())

def dictionary(n, m, k):
    dp = [[0]*(m+1) for _ in range(n+1)]

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

    def construct_string(n, m, k):
        if n == 0:
            return 'z' * m
        if m == 0:
            return 'a' * n
        if k <= dp[n-1][m]:
            return 'a' + construct_string(n-1, m, k)
        else:
            return 'z' + construct_string(n, m-1, k - dp[n-1][m])

    if k > dp[n][m]:
        return -1
    else:
        return construct_string(n, m, k)
    
print(dictionary(n, m, k))

 

코드를 이렇게 구성해보았다.

 

k번째가 어디에 올까를 모두 고민하면 너무 어렵기 때문에, 시작이 'a'가 되는 지점과 'z'가 되는 지점을 나누어 재귀적으로 뒤에 문자열을 붙여주는 방식을 떠올려보았고, 일단 코드를 작성해보았는데 잘 통과가 되었다. 재귀적으로 안 풀렸으면, 하나하나 다 세어보려고 했는데 정말 다행이다... ㅎㅎ