백준 1754 - 진영 순열

icpc.me/1754

A[0]이 입력으로 주어진 이유

$A[0] \geq 0$ 인 순열들에 대해 진영 순열로 변환하면 다음과 같은 모양새를 띠게 된다.

 

0 _ _ _ ... / _ 0 _ _ ... / _ _ 0 _ ... / _ _ _ 0 ...

 

그러면 a + b = c라고 할 때 c-진영 순열이 되는 경우의 수는

 

0 왼쪽에 있는 순열이 a - 1 진영 순열인 경우 * 0 오른쪽에 있는 순열이 b-진영 순열인 경우

 

여기서 0 왼쪽에 있는 순열은 0때문에 기존 진영 순열에서 1 더해지므로 a - 1 진영 순열이어야 한다.

 

A[0]인 경우도 따로 처리해야 한다. 이럴 때는 길이 n의 수열이 c-진영 순열인 경우를 구하면 된다.

진영 순열 구하기

기존에 순열에서 확장하는 것을 생각해보자. 다음 대소 관계를 가지고 있는 1-진영 순열을 보자

 

$a < b < c < d > e < f$

 

여기서 $g > a, b, c, d, e, f$ 인 g를 넣어서 순열을 확장한다고 할 때 여러가지를 관찰할 수 있다.

 

1. k-진영 순열의 맨 앞에 g를 넣어 만든 순열은 k + 1-진영 순열이다.

 

2. k-진영 순열의 맨 뒤에 g를 넣어 만든 순열은 k-진영 순열이다.

 

3. k-진영 순열에서 대소 관계가 B[i] < B[i + 1] 인 두 수 사이에 g를 넣어 만든 순열은 k + 1-진영 순열이다.

 

4. k-진영 순열에서 대소 관계가 B[i] > B[i + 1] 인 두 수 사이에 g를 넣어 만든 순열은 k-진영 순열이다.

 

우리는 3가지의 갈래로 진영 순열이 확장하는 것을 토대로 다음 dp 테이블을 구성할 수 있다.

 

dp[i][j] := 1번부터 i번까지 순증가 관계에 있는 숫자들을 나열한 순열이 j-진영 순열인 경우의 수

 

이때 0-진영 순열이 되는 경우의 수는 수들이 순증가로 주어지는 점을 고려하면 무조건 1임을 알 수 있다.

 

4가지 경우, 그리고 base case를 고려하여 동적계획법을 수행하면 dp 테이블을 완성할 수 있다.

답 구하기

첫 문단을 참조하되, 여러개의 수를 뽑는 경우를 고려하여 이항계수를 곱해줘야 한다.

 

예를 들어 예제로 주어진 7 3 2의 경우

 

_ _ 0 _ _ _ _ 여기에서 0 오른쪽에 6개의 숫자 중 4개를 뽑은 숫자 조합 $\binom{6}{4}$, 진영 순열을 만드는 경우의 수, 0 왼쪽에 나머지 2개의 숫자로 진영 순열을 만들어진 경우의 수를 곱해준다.

 

K-진영 순열을 만족하지 않는데도 더해주는 것을 유의하도록 하자. 구현을 보면 0의 인덱스가 0이 아닐때 i + j + 1 = K인 경우만 계산을 하고 있다.

 

전체 코드

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
int n, k, origin;
int limit_l, limit_r;
 
ll jyp[20][20];
int bino[20][20];
 
int getbino(int n, int r);
 
int main()
{
    cin.tie(0); ios::sync_with_stdio(false);
 
    memset(bino, -1, sizeof bino);
    bino[1][0] = bino[0][0] = 1;
 
    cin >> n >> k >> origin;
    
    limit_l = origin;
    limit_r = n - limit_l - 1;
    
    jyp[0][0] = 1;
 
    for (int i = 1; i < 20; ++i)
    {
        for (int j = 0; j < i; ++j)
        {
            if (!j)
                jyp[i][j] = 1;
            else
                jyp[i][j] = (i - j) * jyp[i - 1][j - 1] + jyp[i - 1][j] * (j + 1);
        }
    }
 
    ll res = 0;
 
    if (!origin)
    {
        res = getbino(n - 1, n - origin - 1) * jyp[limit_r][k];
    }
    else
    {
        for (int i = 0; i <= k; ++i)
            for (int j = 0; j <= k; ++j)
                if (i + j == k - 1)
                    res += getbino(n - 1, n - origin - 1) * jyp[limit_l][i] * jyp[limit_r][j];
    }
 
    cout << res;
}
 
int getbino(int n, int r)
{
    if (n < 0 || r < 0 || n < r)
        return 0;
    
    int &ret = bino[n][r];
 
    if (ret != -1)
        return ret;
    
    return ret = getbino(n - 1, r) + getbino(n - 1, r - 1);
}