[Python 3] BOJ 1256 사전

 

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

1256번: 사전

 

 

오늘의 문제는 사전 이라는 문제이다.

친구의 추천을 받고 문제를 접하게 되었는데, 평소에 확률과 통계 과외를 해왔어서, 바로 중복조합이라는 아이디어를 얻었다.

중복조합이란, 서로 다른 n개 중 k개를 중복을 허용하며 순서를 고려하지 않고 선택하는 것을 말합니다.

이렇게 정의를 보면, 정확하게 와닿기가 쉽지 않다. 

쉽게 생각하면, a,b,c,d  총 4명의 후보가, 그리고 10명의 투표인단이 있다고 생각하자.

4명의 후보를 10명의 투표인단이 뽑는다.

이를 수식으로 정리하면 4H10이라고 정의할 수 있다.

(확률과 통계에서도, 항상 정치인 투표에 비유를 한다. 앞에 오는 것은 뽑힐 수 있는 후보, 뒤에 오는 것은 뽑는 사람들.)

 

n명의 후보, r명의 투표인단.

 

1번 예시를 확인해보자.

 

여기서 _ a _ a _ 처럼, 모든 a 사이에 z들이 총 개수 2개만큼 올 수 있는 틈이 있다고 고려해보자. 

앞에서부터 z를 둘건데, z를 두면, 더 뒷 번호로 가게 된다. z가 0개인것부터 시작한다.

 

맨 앞에 z가 0개이다.  a _ a _ 의 상황이다. 2개의 z를 두 군데에 둘 수 있으므로, 2H2 - > 3개의 경우의 수가 가능하다.

이 경우의 수에 우리가 원하는게 있다. a _ a _ 로 설정하자.

 

맨 앞에 z가 0개이다. a a  _의 상황이다. 1H2 -> 1개의 경우의 수가 가능하다. 1개 남았다.

맨 앞에 z가 1개이다. a z a _ 의 상황이다. 1H1 -> 1 개의 경우의 수가 가능하다. 바로 이게 정답이다.

a z a z가 정답인 이유이다.

 

 

from math import comb
n,m,k=map(int,input().split())
t=comb(n+m,m)
if t>int(1e9) or k<=t:
    k-=1
    while k:
        for i in range(m,-1,-1):
            t=comb(n+i-1,i)
            if t<=k:
                k-=t
                m=i-1
                print("z",end="")
            else:
                break
        print("a",end="")
        n-=1
    print("a"*n,end="")
    print("z"*m,end="")
else:
    print(-1)