사전 - 1256

[Gold II] 사전 - 1256

문제 링크

분류 1️⃣

조합론(combinatorics), 다이나믹 프로그래밍(dp), 수학(math)

문제 설명2️⃣

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

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

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

입력 3️⃣

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

출력 4️⃣

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

풀이 🏆

• ‘a’, ‘z’로 만들 수 있는 문자열 경우의 수가 k 보다 큰 지, 작은 지 판단 할 줄 알아야한다
• 경우의 수를 찾기 위해서 순열을 사용할 수 있지만, 시간이 오래 걸린다 그 대신 DP 테이블을 사용해야 한다.
• 경우의 수가 k보다 크다면 문자열을 찾을 수 있는 거니깐 k번째 문자열을 판단해야 한다.

구현 ✨

• dp[i][j] 는 ‘a’ i개와, ‘z’ j개로 만들 수 있는 문자열의 경우의 수

• dp[i][j]는 문자열 맨 앞에 'a'인 경우의 수 + 문자열 맨 앞에 'z'인 경우의 수

• dp[i][0]은 ‘a’만 i개여서 문자열 경우의 수는 1개, dp[0][j]도 마찬가지

• chk(n, m, k)는 ‘a’ n개와, ‘z’ m개로 만들 수 잇는 문자열 중 사전 순으로 k번 째

코드 📃

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

# dp[x][y] <= a가 x개, z가 y개로 만들 수 있는 경우의 수
dp = [[0 for _ in range(m+1)] for _ in range(n+1)]

# dp[0][i] 은 z밖에 없는 거니깐 만들 수 있는 경우의 수는 1개
for i in range(m+1):
    dp[0][i] = 1

# dp[i][j] 는 'a', 'z'로 만들 수 있는 경우의 수니깐 
# 맨 앞에 'a'가 오는 것으로 만들 수 있는 경우의 수 dp[i-1][j]
# 맨 앞에 'z'가 오는 것으로 만들 수 있는 경우의 수 dp[i][j-1]
# 의 합 
for i in range(1, n+1):
    # dp[i][0] 은 a밖에 없는 거니깐 만들 수 있는 경우의 수는 1개
    dp[i][0] = 1
    for j in range(1, m+1):
        dp[i][j] = dp[i-1][j] + dp[i][j-1]

# n개의 'a'와 m개의 'z'로 만들 수 있는 문자열 중 k번 째
def chk(n, m, k):
    if n == 0:
        print('z'*m)
        return
    elif m == 0:
        print('a'*n)
        return

    # 'a'가 맨 앞에 오는 경우 수dp[i-1][j]와 k를 비교하여
    # k가 더 작으면 맨 앞에 'a'가 위치해야함 
    if dp[n-1][m] >= k :
        print('a', end='')
        chk(n-1, m, k)
    else:
        print('z', end='')
        # 'z'가 맨 앞에 오는 경우 수보다 k가 더 크면
        # 맨 앞에 'z'가 위치해야함
        # 그러나 그 다음 문자를 출력하는데에 있어서
        # z가 앞에 이미 출력되어 있고 뒤에 문자를 판별하는 거니깐
        # 'a'가 맨 앞에 오는 경우의 수를 빼고 k를 전달해야함 
        chk(n, m-1, k-dp[n-1][m])



if dp[n][m] < k:
    print(-1)
else:
    chk(n,m, k)

내가 푼 틀린 코드 😅

import sys

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


def dfs(i, str, a, z):
    global result
    if i == n+m:
        if str not in result:
            result.append(str)
        return
    
    if a:
        n_str = str
        n_str+='a'
        dfs(i+1, n_str, a-1, z)
    if z:
        m_str = str
        m_str+='z'
        dfs(i+1, m_str, a, z-1)



result = []
str = ''
dfs(0, str, n, m)
result.sort()
if len(result) < k:
    print(-1)
else:
    print(result[k-1])

고찰 ✌

dfs로 구현 한 코드는 vscode 상에서 정답이 잘 나왔지만 백준으로 체점을 했을 때 시간초과가 나왔다 그래도 오랜만에 어려운 문제를 내 힘으로 빠르게 풀렷다는 생각에 드디어 알고리즘이 눈에 트이는 구나 생각을 했었는데 시간초과를 해결하지 못했다..

이후 시간초과를 의식하면서 dp로 접근을 했었는데 코드 구현이 어려웠다.. 아직 갈 길이 멀다 그래도 잘하고 있다 재범!!!