[백준 1256] 사전 (with Python / DP)

문제링크

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

1256번: 사전

문제설명

문제

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

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

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

입력

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

출력

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

제한

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

 

문제풀이

문제 분석

- K번째 문자열 구해야한다.

- 주어진 입력값 K가,  만들 수 있는 문자열 조합 개수보다 크다면 -1 출력하자.

- N개의 a와 M개의 z로 만들 수 있는 문자열 조합 경우의 수를 구하자.

 

핵심 아이디어

D[N][M] = N개의 a와 M개의 z로 만들 수 있는 문자열 조합 개수

 

예를들어, N = 2, M = 2, K = 2 라면 가능한 문자열 조합은 다음과 같다.

[ aazz, azaz, azza, zaaz, zaza, zzaa ]

 

그렇다면,

D[N-1][M] 은 무엇을 의미할까?

문자열의 맨앞을 a로 고정한다는 의미.

 

왜?

D[1][2] 일 경우 가능한 조합은 [ azz, zaz, zaa ] ( a가 1개, z가 2개이니까) 로

모두 맨앞에 a를 이어 D[2][2]에 포함될 후보군인 셈이다.

([aazz, azaz, azza] 가 될 예정.)

근데 주어진 K(여기선 2로 가정) 가 저 조합 개수에 포함되므로,

앞자리는 a로 고정.

그리고 N은 1감소하여 N -= 1

 

이런식으로 N, M, K을 조금씩 감소 시키며 문자열의 첫자리부터 알파벳을 하나씩 고정해나간다는 아이디어로 구현해보았다.

 

 

코드

import sys

input = sys.stdin.readline
N, M, K = map(int, input().split())
D = [[0 for _ in range(M+1)] for _ in range(N+1)]
answer = ''

#a와 z중 하나로만 만들 수 있는 문자열 조합 경우의수 전부 1로 초기화
for i in range(N+1):
    D[i][0] = 1
for j in range(M+1):
    D[0][j] = 1 

# 점화식 기반으로 경우의수 계산
for i in range(1, N+1):
    for j in range(1, M+1):
        D[i][j] = D[i-1][j] + D[i][j-1]

maxArr = list(map(max, D))
maxVal = max(maxArr)

if maxVal < K:
    print(-1)
else:
    while N > 0 and M > 0:
        tmp = D[N-1][M] # 현재 타겟 인덱스의 알파벳을 a로 고정했을때, 후보군 경우의수

        if K <= tmp:  # 현재 알파벳을 a로 고정한 인덱스 범위 안에 K가 속해있을때,
            N -= 1  # 그 자리 a로 확정
            answer += 'a'
        else: # K가 더 크다는 말은, a를 고정한 인덱스들의 범위안에 없으므로 z가 되어야한다.
            M -= 1
            K -= tmp
            answer += 'z'

    # N, M 중 하나가 0이 되어 반복문 빠져나오면, 나머지 하나 마저 이어주기
    answer += ('a' * N + 'z' * M)
    print(answer)​