백준 1256번 : 사전

문제 : 백준 1256번

1. 알고리즘 설계

일단 브루탈하게 'a'부터 'z..aa...'까지 문자열들을 모두 구한다는 것은
시간은 물론이고 공간적으로도 불가능하다. (K는 10억이하;;)

그래서 K번째까지 문자열들을 만들고 탐색해서 출력하는 것, 조합식등은 폐기.다음으론 DP를 떠올렸다. 점화식을 구할 수 있을까?

N개 'a'와 M개 'z'로 만들 수 있는 문자열의 개수를 생각해보자.

1. DP[N][M]을 N개의 'a'와 M개의 'z'로 만들 수 있는 문자열의 개수라고 하자.
2. 어떤 문자열은 항상 'a'혹은 'z'로 시작한다.
3. 그렇다면, DP[N-1][M] 은 'a'로 시작하는 문자열의 개수이고,
   DP[N][M-1]은 'z'로 시작하는 문자열의 개수이다.
4. 따라서, DP[N][M] = DP[N-1][M] + DP[N][M-1] 이다.

점화식을 구하고 나니 이제 좀 DP문제처럼 보인다.
DP[1][1]부터 시작해서 DP[N][M]까지 구해서 저장해야 할 것 같다.

다음으로, K번째 문자열은 어떻게 구할 수 있을까?

아까 본 것 처럼 맨 앞자리가 'a'인 문자열의 개수는 DP[N-1][M]이다.
사전순으로 문자열이 나열되므로

DP[N-1][M]개의 'a'로 시작하는 문자열이 사전의 앞 부분에 있고
DP[N][M-1]개의 'z'로 시작하는 문자열은 사전의 뒷 부분에 있을 것이다.

따라서,

DP[N-1][M] 보다
K가 작거나 같다면 : 'a'로 시작하는 문자열이다.
K가 크다면 : 'z'로 시작하는 문자열이다.

이 과정을 K와 N,M을 줄여가며 2번째, 3번째...자리에 대해서 반복하면?
맨 앞자리부터 차례차례 문자를 확정할 수 있다.

2. 구현

N,M,K를 입력받고 메모지에이션을 수행하자.
K번째 문자열을 나타낼 변수도 하나 선언한다.

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

#결과저장용 변수
result = ""
#DP는 DP[0][0] ~ DP[N][M]까지 1로 초기화
DP = [[1 for _ in range(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]

반복문의 논리 구조를 구성해보자.

DP[N-1][M]과 K를 비교한다.
K가 작거나 같다면 :
     첫 자리를 'a'로 확정
     'a'가 1개 줄었으니 N은 1 감소
K가 크다면 :
     첫 자리를 'z'로 확정
     'z'가 1개 줄었으니 M은 1 감소
     첫 자리에 'a'가 들어갈 수 있는 경우만큼 K를 감소시킴
N혹은 M이 0이 되면, 반복문에서 탈출.

코드로 보면 아래와 같다.

while N > 0 and M > 0 :
        tmp = DP[N-1][M]
        if K <= tmp:
            N -= 1
            result += 'a'
        else :
            M -= 1
            result += 'z'
            K -= tmp

반복문을 탈출한 후에는 N 혹은 M이 남아있게 되는데
남은 만큼, 해당하는 문자를 뒤에 붙여주면된다.

    result += 'a' * N + 'z' * M

K가 DP[N][M]을 초과하는 경우에 대해서 걸러주면 문제구현이 끝났다.

전체코드

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

#결과저장용 변수
result = ""
#DP는 DP[0][0] ~ DP[N][M]까지 1로 초기화
DP = [[1 for _ in range(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 :
    result = -1
else :
    while N > 0 and M > 0 :
        #첫자리가 a인 문자열의 개수
        tmp = DP[N-1][M]
        #작거나 같으면
        if K <= tmp:
            #첫자리가 'a'인 것.
            #'a'로 확정하고 N -= 1
            N -= 1
            result += 'a'
        else :
            #첫자리가 'z'인 것.
            #'a'로 확정하고 M -= 1
            #첫 자리가 'a'인 문자열의 수만큼 K 감소
            M -= 1
            result += 'z'
            K -= tmp
    #남은 a,z를 추가해줌
    result += 'a' * N + 'z' * M
#결과출력
print(result)

끝으로

피드백과 질문은 언제나 환영입니다.