BOJ 3948 홍준이의 친위대

* BOJ 3948 홍준이의 친위대

[분류 - 다이나믹 프로그래밍]

[풀이]

  만족하는 나열은 두 종류가 존재한다. 작큰작큰 또는 큰작큰작.

  

  1. 상태를 dp[작큰인지 큰작인지][수열을 구성하는 인원수]로 둔다.

  2. 현재 인원수 i명 계산할 때 인원수 i-1명에서 가장 키가 큰 인원을 넣는다고 생각하자. 이 가장 큰 인원을 기준으로 왼쪽에 설 인원, 오른쪽에 설 인원을 정해보자.

  왼쪽에 있을 인원들의 수가 짝수라면 시작을 큰작으로 시작할 수 밖에 없다. 반면 오른쪽에 있는 인원들은 무조건 작큰으로 시작하면 된다.

  여기서 왼쪽에 배치할 인원을 골라보자. i-1명중 j를 고르게 될텐데, 중요한 점은 어느 j명을 골라도 무조건 j명 배치가 가능하다는 점이다(모두 서로 다른 키를 가지고 있음).

  따라서 i-1명 중 j를 고를 경우의 수는가지 존재한다.

  3. 점화식

    l = 왼쪽 인원수가 짝수라면 큰작이므로 1 홀수라면 작큰이므로 0

    j = 왼쪽 인원수

#include<cstdio>
int main() {
    int T, N, i, j, l, r;
    long long dp[2][21] = {}, nCr[21][21]={1};
    dp[0][0] = dp[1][0] = 1;
    dp[0][1] = 1; // 
    for(i=1;i<21;i++) {
        nCr[i][0] = 1;
        for(j=1;j<=i;j++)
            nCr[i][j] = nCr[i-1][j-1] + nCr[i-1][j];
    }
    for (i = 2; i < 21; i++) {
        for (j = 0; j < i; j++) {
            l = !(j % 2);
            dp[l][i] += dp[l][j] * dp[0][i - 1 - j] * nCr[i-1][j];
        }
    }
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &N);
        printf("%lld\n", i == 1 ? 1 : dp[0][N] + dp[1][N]);
    }
    return 0;
}