백준 1256번 - 사전

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

1256번: 사전

 

필요한 배경지식

• 다이나믹 프로그래밍
• 조합론 - 파스칼 항등식

 

문제 해결 방법

N=2, M=2 일때 나올 수 있는 문자열을 사전순으로 나열하면 다음과 같습니다.

 

1번째 문자열 : aazz

2번째 문자열 : azaz

3번째 문자열 : azza

4번째 문자열 : zaaz

5번째 문자열 : zaza

6번째 문자열 : zzaa

문제에서 K=2로 주어진다면 2번째 문자열인 azaz를 출력해야 합니다. 어떻게 출력해야 할까요 ?

 

첫번째 문자부터 마지막 문자까지 하나씩 출력하여 2번째 문자열을 출력할 수 있는 방법을 생각해 보겠습니다.

위의 경우 첫번째 문자로 'a'가 온다면

남은 문자열로 만들 수 있는 3개의 문자열중 2번째 문자열이 포함되어 있으므로  'a'를 출력,

그 다음 두번째 문자열로 'a'가 온다면

남은 문자열로 1개의 문자열만 만들어 낼 수 있고 이것은 2번째 문자열이 아니므로 'a'대신 'z'를 출력,

그 다음의 문자열들도 같은 방식으로 출력하여 azaz를 출력할 수 있습니다.

 

이제 주어진 'a'와 'z'로 만들어 낼 수 있는 문자열의 개수만 알면 됩니다.

이것은 조합을 이용하면 쉽게 구해낼 수 있습니다.

문자열은 'a'와 'z' 두개뿐이므로 총 문자열의 개수에서 'a'또는 'z'가 위치할 자리의 개수만 뽑으면 됩니다.

예를들어 'a'문자 5개, 'z'문자 3개로 만들 수 있는 문자열의 총 개수를 알고 싶다면 8C5 또는 8C3를 계산하면 되겠죠.

 

이때 조합의 계산은 파스칼 항등식과 DP를 이용하여 구현했고

1 ≤ K ≤ 1,000,000,000 라는 조건이 있기 때문에 조합의 계산 결과가 K의 범위를 넘어가면

INF라는 상수를 반환하도록 구현했습니다.

 

 

전체코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9 + 1;

int N,M,K;
ll dp[210][110]{};

// 탑다운 DP
ll comb(int n, int r) {
    if(n==r || r==0) return 1;
    ll &ret = dp[n][r];
    if(ret==0) {
        ll tmp = comb(n-1, r-1) + comb(n-1, r);
        ret = tmp >= INF ? INF : tmp;
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>N>>M>>K;
    if(comb(N+M,M) < K) {cout<<-1; return 0;}
    
    int cn = N, cm = M, ck = K;
    for(int i=0; i<N+M; i++){
        if(cn==0) {cout<<'z'; continue;}
        ll now = comb(cn+cm-1, cn-1);
        if(now >= ck) {
            cout<<'a';
            cn--;
        } else {
            cout<<'z';
            ck -= now;
            cm--;
        }
    }
}