[Python 3] BOJ - 1256 "사전"

 # 문제 링크

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

1256번: 사전

 

 # 풀이

 개인적으로 이 문제의 핵심은 조합론이라고 생각한다.

<그림 1. 예제 1의 상태 공간>

 문제를 분석하게 되면 결국에 몇번째 문자이건 시작은 A또는 Z임에는 자명하다. cnt[i]를 현재 길이가 i일 때 가능한 모든 문자열의 갯수라고 정의하자. 그렇다면 현재 그림 1의 가장 왼쪽은 수평선을 기준으로 위쪽 부분은 A로 시작하며, 아래쪽 부분은 Z로 시작함을 알 수 있다. 그런데, 어느 쪽이든 시작하는 부분을 선택하고 그 다음 경우에 가능한 모든 문자열의 갯수는 cnt[i-1]과 같음을 알 수 있다. 다시 말해, 현재 A가 2개이고 Z가 2개일 때, 첫 시작문자를 A로 하나 Z로 하나 결국에는 총 4개의 알파벳 중 하나를 빼는 것이고, 총 알파벳의 갯수는 3개라는 것이다.

 그런데, 만일 A를 빼게 되면 그 다음 문자열의 경우는 A가 1개, Z가 2개로 이루어지며, Z를 빼게 되면 그 다음 문자열의 경우는 A가 2개, Z가 1개로 달라지게 된다. 그런데 A를 빼게 된다는 것은 이후 A가 1개, Z가 2개가 남는다는 뜻이다. 그런데 남는 A와 Z를 사전 순으로 정렬하는 경우의 수는 남는 A와 Z를 합한 경우에서 A를 사전 순으로 배열하는 것과 같으며 결국에는 (A와 Z를 합친 모든 갯수) Combination (A의 갯수)와 같다. 따라서 그림 1의 경우는 3C1과 같다. 

 따라서, K번째 문자열이 경계선이 위치한 곳보다 작거나 같다면 A를 뽑는 것이고, 그렇지 않다면 Z를 뽑는 것과 마찬가지이다. 이 때 A를 이미 다 뽑아버렸다면 경계는 0이 됨에 주의하자. 역시 전체 경우의 수보다 K가 크다면 문자열을 만들 수 없으므로 이 때는 문제의 조건에 따라 -1을 출력하면 정답을 구할 수 있다

 

# 코드

import sys, math

# count : (n+m) C (n)을 리턴하는 함수
def count(n,m):
    return math.factorial(n + m) // (math.factorial(n) * math.factorial(m))

# go : 현재 num번째 문자열, 남은 A의 갯수가 cnt_a, 남은 Z의 갯수가 cnt_z일 때 조건을 만족하는
#      문자열 res를 채우는 함수

def go(num, cnt_a, cnt_z, res):
    # Base Case : 현재 A와 Z가 아무것도 없는 경우 = 다 뽑은 경우
    if cnt_a < 1 and cnt_z < 1:
        return
        
    # A가 1개 이상인 경우 경계값 계산
    if cnt_a >= 1:
        border = count(cnt_a - 1, cnt_z)
    # A를 다 뽑은 경우는 경계값이 0
    else:
        border = 0
        
    # 현재 뽑아야 하는 num번째 수가 경계보다 같거나 작은 경우는 A를 뽑는다
    if border >= num:
        res.append('a')
        go(num, cnt_a - 1, cnt_z, res)
        
    # 그렇지 않으면 z를 뽑는다
    else:
        res.append('z')
        # num에서 border를 왜 빼야 하나?
        # A가 아닌 Z를 뽑아야 하므로 이전에 A가 차지했던 부분은 더이상 유효하지 않기 때문
        go(num - border, cnt_a, cnt_z - 1, res)

# 입력부
n, m, k = map(int, sys.stdin.readline().split())

# K가 전체 경우보다 크면 -1
if count(n,m) < k:
    print(-1)
    
# 정답 출력
else:
    ans = []
    go(k, n, m, ans)
    print(''.join(ans))