728x90
1256번: 사전
동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 김진영 조교는 동호와 규완이에게 특별 과제를 주었다. 특별 과제는 특별한 문자열로 이루어 진 사전을 만드는 것이다. 사전에 수록되
www.acmicpc.net
분석
- n개의 "a", m개의 "z", k번째 문자열 출력
- 조합점화식 : dp[i][j] = dp[i-1][j]+dp[i-1][j-1]
- 현재 자릿수에서 a를 선택했을 때 남아 있는 문자들로 만들 수 있는 모든 경우의 수를 T라고 가정
- 나머지 문자열을 만들 수 있는 경우의 수 = D[남은문자 총개수][남은 z개수]
- T와 K를 비교해 문자 선택
- T ≥ K : 현재 자리 문자를 a로 선택
- T < K : 현재 자리 문자를 z로 선택하고, K-=T로 업데이트
N = 3, M = 2, K = 4인 경우
aaazz aazaz aazza azaaz azaza azzaa zaaaz zazaa zaaza zzaaa
1. a를 선택한 경우, 나머지 문자열을 만들 수 있는 경우의 수 D[4][2] = 6 ≥ 4 ➔ a 선택
a
2. a를 선택한 경우, 나머지 문자열을 만들 수 있는 경우의 수 D[3][2] = 3 < 4 ➔ z 선택, K=1
az
3. a를 선택한 경우, 나머지 문자열을 만들 수 있는 경우의 수 D[2][1] = 2 ≥ 1 ➔ a 선택
aza
4. a를 선택한 경우, 나머지 문자열을 만들 수 있는 경우의 수 D[1][1] = 1 ≥ 1 ➔ a 선택
azaa
5. a를 선택한 경우, 나머지 문자열을 만들 수 있는 경우의 수 D[0][1] = 0 < 1 ➔ z 선택, K=1
azaaz
풀이
"""
특별한 문자열로 이뤄진 사전 만들기
사전에 수록돼 있는 문자열은 N(1~100)개의 a, M개의 z
알파벳 순서대로 수록
k(1,000,000,000)번째 문자열 출력
"""
import sys
input = sys.stdin.readline
n,m,k=map(int,input().split())
d = [[0 for i in range(202)] for j in range(202)]
# 조합 테이블 생성
for i in range(0,201):
for j in range(0,i+1):
if i==0 or i==j:
d[i][j]=1
else:
# 조합 점화식
d[i][j] = d[i-1][j]+d[i-1][j-1]
if d[i][j] > 1000000000:
d[i][j] = 10000000001 # k범위가 넘어가면 범위의 최댓값 저장
if d[n+m][m] < k: # 주어진 자릿수로 만들 수 없는 k번째 수의 경우
print(-1)
else: # 문자 선택
while not (n==0 and m==0): # 모든 문자를 사용할 때까지
#d[n-1+m][m] : a문자를 선택했을 때 남은 문자열들로 만들 수 있는 모든 경우의 수
if d[n-1+m][m] >= k: # a를 선택해도 남은 경우의 수가 k보다 큰 경우
print("a", end='')
n-=1
else:
print("z", end='')
k-=d[n-1+m][m] # k의 값을 계산된 모든 경우의 수를 뺀 값으로 저장
m-=1728x90