[백준 1256] 사전 (python)

1256번: 사전

---

 

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

 

1. 만들 수 있는 단어 개수를 저장하는 arr[a의 개수][z의 개수]를 생성한다.
2. a로만 이루어진 단어와 z로만 이루어진 단어는 1개뿐이므로 arr[?][1] = arr[1][?] = 1이다.
3. DP를 통해 arr[i][j]는 a를 하나 뺀 단어(arr[i-1][j])와 z를 하나 뺀 단어(arr[i][j-1])를 합치면 된다.
4. K가 더크다면 -1을 출력한다.
5. 제일 앞 알파벳이 a라고 했을 때 가질 수 있는 단어 개수는 arr[N-1][M] 개이다.
6. K가 arr[N-1][M]보다 작거나 같다면 앞 알파벳이 a이고, 크다면 z이다.
7. 이런식으로 앞에서부터 알파벳을 정해 결과를 출력해준다.

 

import sys
input = sys.stdin.readline

N, M, K = map(int, input().split())
arr = [[1]*(M+1) for _ in range(N+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]

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)