[BOJ/C++] 1256 사전

아이디어를 떠올리기 힘들었던 문제입니다.

우선 N개의 a와 M개의 z로 만들 수 있는 조합은 (N+M)개 중에 N개 혹은 M개를 뽑는 조합의 경우의 수와 같습니다.

예를 들어, 2개의 a와 2개의 z로 만들 수 있는 경우의 수는 4개 중에 2개를 뽑는 것과 같습니다.

• 남은 2개의 z는 같기 때문에 어디에 놓더라도 경우의 수가 증가하지 않습니다

다음과 같은 경우의 수가 있습니다.

aazz
azaz
azza
zaaz
zaza
zzaa

그 다음 조합 점화식을 이용해 DP 테이블을 초기화 합니다.

$DP[i][j] = DP[i-1][j] + DP[i-1][j-1]$

이후 K번째에 어떤 문자열이 있는지 알아봅시다.

앞에서부터 하나씩 정하면서 남은 자리수의 경우의 수와 K를 비교합니다.

예를 들어, 2번째인 경우 앞자리를 a로 정하고 시작합니다.

이후 3자리에 z가 2개가 올 수 있고 해당 경우의 수는 $DP[3][2]$가 됩니다.

K와 비교했을 때 $DP[3][2] >= K$ 은 3>=2에 성립하므로 첫 번째 자리에 a가 올 수 있습니다.

a _ _ _ 인 상태에서 만들 수 있는 경우의 수가 3이라는 것이고 K보다 크다면 맨 앞자리에 a가 와도 좋다는 뜻입니다.

만약 K가 6이라면 3>=6에 성립하지 않는데 이것은 a _ _ _ 로 만들 수 있는 경우의 수가 3 즉 3개를 만들 수 있지만 6번째를 찾아야하기 때문에 맨 앞자리에 a가 오면 안된다는 뜻입니다.

맨 앞자리를 z로 바꾸고 a _ _ _ 로 올 수 있는 경우의 수 $DP[3][2]$가 배제된 것이므로 K에서 빼줍니다.

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <string>
#include <climits>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>

using namespace std;

using int32 = long;
using int64 = long long;

static int DP[201][201] = {};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    
    int N, M, K;
    cin >> N >> M >> K;

    // Init DP table
    for(int i=0; i<=N+M; i++)
    {
	    for(int j=0; j<=i; j++)
	    {
            if (j==0 || i == j)
                DP[i][j] = 1;
            else
            {
                DP[i][j] = DP[i - 1][j] + DP[i - 1][j - 1];
                if (DP[i][j] > 1000000000)
                    DP[i][j] = 1000000001;
            }
	    }
    }

    if (DP[N + M][M] < K)
    {
        cout << -1;
    }
    else
    {
        while(!(N==0 && M==0))
        {
            if (DP[N-1 + M][M] >= K)
            {
                cout << 'a';
                N--;
            }
            else
            {
                K -= DP[N-1 + M][M];
                cout << 'z';
                M--;
            }
        }
    }



    return 0;
}