기록하는삶
[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 1256번 _ 사전 본문
https://www.acmicpc.net/problem/1256
[문제]
동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 김진영 조교는 동호와 규완이에게 특별 과제를 주었다. 특별 과제는 특별한 문자열로 이루어 진 사전을 만드는 것이다. 사전에 수록되어 있는 모든 문자열은 N개의 "a"와 M개의 "z"로 이루어져 있다. 그리고 다른 문자는 없다. 사전에는 알파벳 순서대로 수록되어 있다.
규완이는 사전을 완성했지만, 동호는 사전을 완성하지 못했다. 동호는 자신의 과제를 끝내기 위해서 규완이의 사전을 몰래 참조하기로 했다. 동호는 규완이가 자리를 비운 사이에 몰래 사전을 보려고 하기 때문에, 문자열 하나만 찾을 여유밖에 없다.
N과 M이 주어졌을 때, 규완이의 사전에서 K번째 문자열이 무엇인지 구하는 프로그램을 작성하시오.
[입력]
첫째 줄에 세 정수 N, M, K가 순서대로 주어진다.
[출력]
첫째 줄에 규완이의 사전에서 K번째 문자열을 출력한다. 만약 규완이의 사전에 수록되어 있는 문자열의 개수가 K보다 작으면 -1을 출력한다.
[제한]
- 1 ≤ N, M ≤ 100
- 1 ≤ K ≤ 1,000,000,000
[아이디어]
1) 처음에는 그냥 가능한 조합의 정렬에서 k번째를 찾는 단순한 접근을 했는데, 다루는 수가 너무 커서 메모리 초과가 났다.
2) 경우의 수만 따져가며 앞에서부터 문자열을 채우는 것이 핵심이다.
3) n,m개의 문자로 구성할 수 있는 문자열의 수는 math.comb(n+m,n)과 같다. a의 자리를 결정하면 나머지를 z로 채우면 되기 때문이다.
4) n,m에 대해, (n-1)개의 a와 m개의 z로 만들 수 있는 문자열의 수인 math.comb(n+m-1,n-1)보다 k의 값이 크다면, 맨 앞 문자는 a이고, 그렇지 않다면 z이다. 이때 맨 앞을 a로 채웠다면 k의 값을 업데이트한다.
5) 4)의 과정을 반복하여 n,m 둘 중 하나가 0이되거나 k의 값이 0이될 때까지 반복하며 문자열을 채워나가고, 남은 문자가 있다면 그 개수만큼 뒤에 붙여준다.
from math import comb as c
a,b,i=map(int,input().split())
s =["z"]*(a+b)
if c(a+b,a)<i:print(-1)
else:
ans=""
while i and (a and b):
if i > c(a+b-1,a-1):
ans+="z"
i-=c(a+b-1,a-1)
b-=1
else:
ans+="a"
a-=1
print(ans + "a"*a +"z"*b)
꽤 짧길래 숏코딩도 만들어봤다.
from math import comb as c
a,b,i=map(int,input().split());s=""
if c(a+b,a)<i:print(-1)
else:
while i and (a and b):
if i>(t:=c(a+b-1,a-1)):
s+="z";i-=t;b-=1
else:s+="a";a-=1
print(s+"a"*a+"z"*b)
'백준(Python) > 수학(Mathematics)' 카테고리의 다른 글
[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 3955번 _ 캔디 분배 (0) | 2022.04.07 |
---|---|
[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 10986번 _ 나머지 합 (0) | 2022.04.06 |
[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 13172번 _ Σ (0) | 2022.02.12 |
[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 2749번 & 11444번 _ 피보나치 수 3, 6 (0) | 2022.01.31 |
[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 2407번 _ 조합 (0) | 2022.01.24 |