[백준] 1256번 : 사전

1256번: 사전

1256번: 사전

🤔 문제분석

해당문제는 다이나믹 프로그래밍을 역추적 하는 방법으로 문제를 해결 할 수 있습니다. 경우의 수 점화식은 아래와 같이 만들 수 있습니다. 앞에 ‘a’ 가 추가된경우, 앞에 ‘z’가 추가된경우를 둘다 더한값입니다.

여기서 알 수 있는것은 dp[N-1][M]은 ‘a’를 앞에 추가한 것 이고, dp[N][M-1]은 ‘z’를 추가한 것 입니다.

dp[N][M] = dp[N-1][M] + dp[N][M-1]

따라서 재귀 함수를 아래와 같이 선언 할 수 있습니다. 만약 현재의 카운트가 dp[a-1][z] 보다 작다면, a에서 추가된 것임으로, 문자열앞에 ‘a’를 추가합니다. 그렇지 않은경우 ‘z’에서 추가된 경우이고, 앞에 a가 있는경우를 모두 제거하기위하여 cnt 값을 dp[a-1][z]를 빼주어야합니다. 종료 조건은 a혹은 z가 0인경우 남은 개수를 모두 출력합니다.

def dfs(a, z, cnt):
    if a == 0 or z == 0:
        if a == 0:
            return 'z'*z
        else:
            return 'a'*a
    
    if dp[a-1][z] >= cnt:
        return 'a' + dfs(a-1, z, cnt)
    else:
        return 'z' + dfs(a, z-1, cnt - dp[a-1][z])

💻 코드

예외 조건으로 현재의 카운트로 개수를 셀 수 없을경우에는 -1을 출력해주는 예외조건을 만들어줍니다.

import sys
input = sys.stdin.readline

N, M, K = map(int, input().split())

dp = [[0 for _ in range(M+1)] for _ in range(N+1)]

for i in range(1, M+1):
    dp[0][i] = 1
    
for i in range(1, N+1):
    dp[i][0] = 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 dfs(a, z, cnt):
    if a == 0 or z == 0:
        if a == 0:
            return 'z'*z
        else:
            return 'a'*a
    
    if dp[a-1][z] >= cnt:
        return 'a' + dfs(a-1, z, cnt)
    else:
        return 'z' + dfs(a, z-1, cnt - dp[a-1][z])
    
if dp[N][M] >= K:
    print(dfs(N, M, K)) 
else:
    print(-1)

🎯 피드백 및 개선사항

점화식을 도출하는 과정을 역추적 하는 문제로, 경우의 수를 구하는 조건을 잘 간파하고 있다면 해당 문제를 쉽게 풀 수 있을거라고 생각합니다.