[백준(파이썬/Python)] 1256_사전

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

1256번: 사전

 

- 고민을 정말 많이 한 문제입니다. 이틀정도 고민을 하다가 카테고리를 봤고 DP 카테고리인 것을 알았지만 이 문제에서 DP를 어떻게 적용하나싶었고... 결국 원래 생각하던 방식으로 문제를 해결했습니다.

 

- 문제를 푸는 아이디어는 아래와 같습니다.

 

1) 0과 1이 각각 3개씩 존재한다고 생각해보면, 사전에서 가장 앞에 오는 경우는 000111입니다. 그리고 사전에 가장 마지막에 오는 문자는 111000입니다.

2) 만약 맨 앞에 0을 배치한다고 하면, 남은 0은 2개이고 1은 3개입니다. 

* 3) 이 때, K보다 경우의 수가 많다면 0을 앞으로 빼서 사전의 앞쪽을 채워야 합니다.

* 4) 반면, K보다 경우의 수가 적다면 1을 앞으로 빼서 사전의 뒤쪽으로 넘어가야 합니다.

3), 4)번의 논리대로 코드를 작성하면 됩니다.

 

[풀이]

from math import factorial

def getNumOfCombinations(n, m):
    return factorial(n+m) / (factorial(n) * factorial(m))

# 0: n개, 1: m개
n, m, k = map(int, input().split())


# k번째 문자열을 만들 수 없는 경우
if getNumOfCombinations(n,m) < k:
    answer = -1

else:
    k -= 1
    answer = ""

    while True:
        if n == 0 or m == 0:
            break

        numOfCase = getNumOfCombinations(n-1, m)

        # 앞에 0을 붙였을 때 경우의 수가 더 많으면 무조건 0을 앞으로 해야함
        if k < numOfCase:
            answer += "a"
            n -= 1
        # 앞에 0일 때 경우의 수가 부족하다 = 1을 앞쪽으로 배치해야 한다.
        else:
            answer += "z"
            m -= 1
            k -= numOfCase

    # 남은 z나 a를 이어붙여준다.
    answer += "z" * m + "a" * n


print(answer)