[수학/파이썬] 백준 1256번 : 사전 / 골드3

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

1256번: 사전

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

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

for i in range(1, length+1):
    dp[i][0] = 1
    dp[i][i] = 1

for i in range(2, length+1):
    for j in range(1, length+1):
        dp[i][j] = dp[i-1][j-1] + dp[i-1][j]  #  iCj = i-1Cj-1 + i-1Cj

if dp[n+m][n] < k:
    print(-1)
    quit()

answer = ''
while m*n > 0:
    val = dp[n+m-1][n-1]
    if val < k:
        answer += 'z'
        m -= 1
        k -= val

    elif val > k:
        answer += 'a'
        n -= 1
    else:
        answer += 'a'
        n -= 1
        break

for _ in range(m):
    answer += 'z'
for _ in range(n):
    answer += 'a'
print(answer)

다이나믹 프로그래밍으로 nCr을 빠르게 뽑아주는 것만 해결하면 어느 정도 길이 보이는 문제다. 파스칼 삼각형 공식을 이용해서 사용할 수 있는 nCr 값들을 미리 다 구해놓는다.

 

<핵심 아이디어>

내가 a를 택한다면 뒤에 나올 수 있는 총 경우의 수는 n+m-1Cn-1개다.

만약 k가 이 값보다 작다면? => a를 놓는 게 맞다.

만약 k가 이 값보다 크다면? => z를 놓아야 한다. 그리고 k는 k= k- n+m-1Cn-1로 바뀐다.

만약 k가 이 값과 같다면? => k번째를 딱 찾아낸 것이다. a를 일단 1개 넣고, 남은 z를 다 넣고, 남은 a를 다 넣는다.