[BOJ, 백준] 1256 사전 Python

dp로 풀 수 있는 문제다.

솔직히 시간과 메모리만 충분하다면 itertools로 간단하게 계산할 수도 있지만, 더욱 편리함을 위해서 dp로 해결하고자 한다.

 

문제는 이하와 같다.

 

 

즉, 제한된 갯수의 a와 z가 있는 상황에서 K번째 문자열은 무엇인가? 라는 문제가 되겠다.

 

이 문제를 조금 꼬아서 낸다면 a와 z를 전부 사용하지 "않는" 경우에 대해서 생각해보는 것도 재밌을 것 같다.

 

일단 주어진 문제에 충실해지기로 한다면, 해답은 다음과 같다.

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

def f(k):
    # 문자열 개수 초과하는 경우
    t = math.factorial(N+M) // (math.factorial(N) * math.factorial(M))
    if t < k:
        return -1
    dp = [[1 for _ in range(0, M + 1)] for _ in range(0, N + 1)]
    dp[0][0] = 0

    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]

    answer = ""
    n, m = N, M
    while (n > 0 or m > 0):
        if (n == 0 or m == 0):
            answer += 'a' * n
            answer += 'z' * m
            break
        else:
            if k <= dp[n - 1][m]:
                answer += "a"
                n -= 1
            else:
                k -= dp[n - 1][m]
                answer += "z"
                m -= 1
    return answer

print(f(K))

 

첫번째 분기에서, 먼저 K가 만들 수 있는 index인지 판단하는 알고리즘을 넣어준다.

 

만들 수 있는 index라는 것을 알게 되었다면, dp를 만들어 준다.

dp를 만들어준 이후에는 이 문자열이 어디쯤에 위치해있는지 확인해볼 필요가 있다.

 

a로 시작하는 문자열은 "반드시" z로 시작하는 문자열보다 앞에 오기 때문에, 다음과 같은 방식으로 분기를 나눠주면 되겠다.

 

조금 더 풀어쓰면, dp[n][m] = dp[n-1][m] + dp[n][m-1]로 이루어지는데

dp[n-1][m]은 a를 n-1개, z를 m개 쓴 문자열이고 dp[n][m-1]은 a를 n개, z를 m-1개 쓴 문자열들의 갯수이다.

 

즉, dp[n][m]은 dp[n-1][m]에 포함된 문자열의 가장 앞에 "a"를 붙인 것이고 (이 다음에 !)

dp[n][m-1]에 포함된 문자열의 가장 앞에 "z"가 붙여진 것들로서 이루어진다고 볼 수 있겠다.

 

위에서 설명했듯이, dp[n][m]에 포함된 친구들을 생각해본다면

"a" + dp[n-1][m][0] , ...., "a" + dp[n-1][m][-1]     < a로 시작하는 애들 

"z" + dp[n][m-1][0] , ...., "z" + dp[n][m-1][-1]     < z로 시작하는 애들

 

이 순서대로 정렬되어있다는 것을 확인할 수 있겠다.

 

이러한 방식으로 점점 K가 어디에 존재하는지 확인하는 방식으로 진행하면 되겠다.