[백준/1256/파이썬] 사전

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

1256번: 사전

Problem

• 사전에 수록되어 있는 모든 문자열은 N개의 "a"와 M개의 "z"로 이루어져 있다. 
• 그리고 다른 문자는 없다. 사전에는 알파벳 순서대로 수록되어 있다.
• N과 M이 주어졌을 때, 규완이의 사전에서 K번째 문자열이 무엇인지 구하는 프로그램을 작성하시오.

조건

• 첫째 줄에 세 정수 N, M, K가 순서대로 주어진다.
• 첫째 줄에 규완이의 사전에서 K번째 문자열을 출력한다. 만약 규완이의 사전에 수록되어 있는 문자열의 개수가 K보다 작으면 -1을 출력한다.
• 1 ≤ N, M ≤ 100
• 1 ≤ K ≤ 1,000,000,000

SOL

어려운 개념이 2개가 섞여있다.

시뮬레이션 문제는 입력에 있는 예시로 어떻게 구분하면 좋을지 insight를 얻어간다.

• a=2,z=2개 있을때, 가능한 모든 경우는 4!/2!*2!으로, 중복순열의 경우의 수라고 생각할 수 있다.
• 그리고, K번째 숫자를 어떻게 알아낼까 생각해보니까, 글자는 "a"또는 "z"로 시작이 된다.
• 즉, 순서대로 쫙 나열했을 때, 정확이 반은 a로 시작할거고, 나머지는 z로 시작할거다.

예를들어, a=2,z=2일 때, 모든 경우를 사전순으로 나열해보면

1. aazz
2. azaz
3. azza
4. zaaz
5. zaza
6. zzaa

k=2니까, K는 "a"로 시작하는걸 알 수 있다. 우리는 모든 경우의 수와 하나의 기준이 필요하다.

이 기준을 "a"로 시작하냐/안하냐로 하겠음!

 

그렇다면, 모든 경우의수는 어떻게 구할 수 있을까?

모든 경우의 수는 중복순열인데, factorial을 컴퓨터로 구현하면 매우 느리기 때문에, factorial을 DP table로 구현할 수 있다. 이렇게 생각하면 쉽다. 모든 경우의 수는 A 또는 Z로 끝나게 된다.

즉, (N-1+M) + "A" , (N+M-1) +"Z"로 되고, N,M에 대한 함수로 나타내어 주면 아래와 같은 점화식이 쉽게 나온다.

• F(N,M) : N개의 "a"와 M개의 "z"로 만들 수 있는 경우의 수 
• F(N,M) = F(N-1,M) +F(N,M-1)
• DP[N][M] = DP[N-1][M] +DP[N][M-1] #table로 표현한다면 옆과같이 된다.

이렇게 해서, 전체 경우의 수는 구할 수 있게 됬다. 전체경우의 수에서, 우리가 기준으로 사용하기로 했던,"a"로 시작하냐,안하냐의 기준은 DP[N-1][M]이 적절하다. DP[N-1][M]보다 작거나 같으면 a로 시작할거고, 아니면 z로 시작할거기 때문! 

 

정리하자면,

if) K<=DP[N-1][M] 이면, K번째 수는 "a"로 시작한다.

else) K> DP[N-1][M] 이면, K번째 수는 "z"로 시작한다.이때, k-=flag를 해줘야한다!

• K번째 수도, 사전순으로 K번째 수였으므로, K가 Z로 시작하면, K= K-flag를 해줘야한다. 이건 예시를 들어보면 쉽게 알 수 있음. 예를들어, N=2,M=2, K=5 일때, K는 3보다 크므로, K는 Z 시작한다. 하지만, z로 시작하는 것중에 5번째는 없다. 즉,"z"로 시작한다면, 앞의 a로 시작하는 경우의 수는 빼줘야한다.

#binary search + DP
import math
N,M,K = map(int,input().split())
DP=[[1]*(M+1) for _ in range(N+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]

if DP[N][M]<K:
    print(-1)
else:
    word=""
    while True:
        if N==0 or M==0:
            word+="z"*M
            word+="a"*N
            break
        #기준은 , a로 시작하냐 ,안하냐이다.
        flag = DP[N-1][M]
        if K<=flag:
            word+="a"
            N-=1
        else:
            word +="z"
            M-=1
            K-=flag
    print(word)