[Python] 백준 1256번: 사전

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

1256번: 사전

 

import sys
input = sys.stdin.readline

if __name__ == '__main__':
    N, M, K = map(int, input().split())

    # Set counts
    counts = [[1]*(M+1) for _ in range(N+1)]

    for i in range(1, N+1):
        for j in range(1, M+1):
            counts[i][j] = counts[i-1][j] + counts[i][j-1]

    # Print
    if counts[N][M] < K:
        print(-1)
    else:
        to_print = ""

        while True:
            if N == 0 or M == 0:
                to_print += "a"*N + "z"*M
                break

            cnt = counts[N-1][M]
            if cnt >= K:
                to_print += "a"
                N -= 1
            else:
                to_print += "z"
                M -= 1
                K -= cnt

        print(to_print)

 

순차적으로 1,000,000,000번을 돌기에는 시간이 부족하다. 따라서 counts라는 리스트를 사용한다. counts[A][Z]는 a가 A개, z가 Z개 있을 때의 경우의 수이다. counts[1][X] 또는 counts[X][1]은 1이며, counts[A][Z] = counts[A-1][Z] + counts[A][Z-1]이 성립한다. 이를 통해 해당 리스트를 초기화해준다. 아래는 예제 입력 1의 counts이다.

 

다음으로 N, M을 0까지 줄여가면서 출력하게 될 to_print를 완성시켜나간다. a를 두었다고 가정(counts[N-1][M])했을 때의 counts를 K와 비교하여, a를 넣을지, z를 넣을지를 결정한다.