[백준/1256] 사전 (Python)

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

1256번: 사전

 

Difficulty : Gold 2

 

Status : Solved

 

Time : 00:19:41

 

---

 

문제 설명

 

 

동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 김진영 조교는 동호와 규완이에게 특별 과제를 주었다. 특별 과제는 특별한 문자열로 이루어 진 사전을 만드는 것이다. 사전에 수록되어 있는 모든 문자열은 N개의 "a"와 M개의 "z"로 이루어져 있다. 그리고 다른 문자는 없다. 사전에는 알파벳 순서대로 수록되어 있다.

규완이는 사전을 완성했지만, 동호는 사전을 완성하지 못했다. 동호는 자신의 과제를 끝내기 위해서 규완이의 사전을 몰래 참조하기로 했다. 동호는 규완이가 자리를 비운 사이에 몰래 사전을 보려고 하기 때문에, 문자열 하나만 찾을 여유밖에 없다.

N과 M이 주어졌을 때, 규완이의 사전에서 K번째 문자열이 무엇인지 구하는 프로그램을 작성하시오.

 

 

입력 및 출력

 

입력

 

첫째 줄에 세 정수 N, M, K가 순서대로 주어진다.

 

출력

 

첫째 줄에 규완이의 사전에서 K번째 문자열을 출력한다. 만약 규완이의 사전에 수록되어 있는 문자열의 개수가 K보다 작으면 -1을 출력한다.

 

• 1 ≤ N, M ≤ 100
• 1 ≤ K ≤ 1,000,000,000

 

입력 예시

 

2 2 2

 

 

출력 예시

 

azaz

 

 

 

---

 

풀이

 

이 문제의 총 경우의 수는 어떻게 표현할 수 있을까? 문제를 변형하여, M개의 'z'의 빈 칸(총 M+1)에 N개의 'a'를 순서 상관 없이 집어넣는 경우의 수라고 볼 수 있겠다. 즉 중복조합이다.

n = M+1, r = N인 상황이므로 다음과 같이 표현된다.

 

즉 K가 이 값보다 크다면 범위를 벗어난 것이므로 -1을 출력하고 종료하면 되겠다.

 

또한, 사전순으로 앞에 오려면 가급적 앞자리에 a가 와야 한다. 가령, 첫 번째 자리(즉 맨 첫 'z'앞에 오는 빈 자리)에 a개의 'a'가 온다고 가정하자. 그렇다면 남은 M-1개의 'z'의 빈 칸에 N-a개의 'a'를 배치하는 경우의 수가 배정된다. 즉 모든 조합 결과를 알고 있다는 전제 하에, O(MN)의 시간복잡도 내에 적절한 K에 해당하는 문자열을 그리디하게 찾아 줄 수 있다.

 

또한, 조합 결과는 바텀업 방식의 DP로 구해줄 수 있다.

이런 식으로 모든 조합을 미리 구해놓을 수 있다. 우리는 N+M 범위까지 필요하므로 이 때의 시간복잡도는 O((N+M)^2)가 된다.

 

풀이 코드

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

combinations = [[0]*(N+M+1) for _ in range(N+M+1)]

combinations[0][0] = 1

for i in range(1, N+M+1) :
  for j in range(i+1) :
    if i == 0 or i == j :
      combinations[i][j] = 1
    else :
      combinations[i][j] = combinations[i-1][j-1] + combinations[i-1][j]

if combinations[N+M][N] < K :
  print(-1)
  exit()

answer = ''
left_a, left_k = N, K
for i in range(M-1, -1, -1) :
  for j in range(left_a, -1, -1) :
    if combinations[left_a-j+i][left_a-j] < left_k :
      left_k -= combinations[left_a-j+i][left_a-j]
    else :
      answer += 'a'*j
      left_a -= j
      break
  answer += 'z'

answer += 'a'*left_a
print(answer)

풀이 완료!