BOJ-3948 홍준이의 친위대

필요한 지식

1. 동적계획법

접근

• 그들을 일렬로 세울 때, 맨 끝 두 병사를 제외한 나머지 병사들의 양 옆 두 병사의 키가 자신 보다 크거나 모두 자신보다 작도록 배치하는 경우의 수를 구해야 한다.

• 양 옆보다 작은 수를 ▲ 양옆보다 큰수를 ●, 추가하려고 하는 수를 X 라고 표시하면 i번째 상태에서 i+1번째 병사가 배치 가능한 경우를 살펴보자.

• i가 3일때

  • ▲●▲X
  • ●▲X▲
  • ▲X▲●
  • X▲●▲ 의 경우가 있고,

• i가 2일때

  • ●▲X
  • ▲X▲
  • X▲● 의 경우가 있다.

• X 양옆으로는 무조건 ▲가 와야하는 것을 볼수 있다.

• 이제 X를 기준으로 양옆으로 분리 시키고 i+1이 짝수일때, 홀수일때 각각을 살펴보면 크게 4가지의 경우로 분류가 가능하다.

  • ▲● : 짝수일때, ▲로 시작
  • ●▲ : 짝수일때, ▲로 끝남
  • ▲●▲ : 홀수일때, ▲가 시작과 끝에 존재
  • ●▲● : 홀수일때, ●가 시작과 끝에 존재

• 위 경우에서 1,3 경우를 j가 0일때, 2,4 경우를 j가 1일때 로 저장한다.

코드(C++)

#include <bits/stdc++.h>
#define FIO ios_base::sync_with_stdio(0), cin.tie(), cout.tie();
using namespace std;
typedef long long ll;
ll combi[30][21], dp[30][2], n, t;

ll getCombi(ll n, ll r) {
    if(n<r || n<=0) return 0;
    if (r == 1) return n;
    if (r == 0) return 1;
    if (r > n / 2) r = n - r;
    ll& ret = combi[n][r];
    if (ret != -1) return ret;
    return ret = getCombi(n - 1, r) + getCombi(n - 1, r - 1);
}

int main() {
    FIO;
    for(int i=0;i<20;i++)memset(combi[i], -1, sizeof(combi[i]));
    cin >> t;
    dp[1][0] = dp[2][0] = dp[2][1] = dp[0][0] = dp[0][1] = 1;
    for (ll i = 3; i <= 20; i++) {
        for (ll k = 1; k <= i; k++) {
            if (i % 2 == 0) {
                if (k % 2 == 0) dp[i][0] += dp[k - 1][0] * dp[i - k][0] * getCombi(i - 1, k - 1);
                else dp[i][1] += dp[k - 1][1] * dp[i - k][0] * getCombi(i - 1, k - 1);
            }
            else {
                if (k % 2 == 0) dp[i][0] += dp[k - 1][0] * dp[i - k][0] * getCombi(i - 1, k - 1);
                else dp[i][1] += dp[k - 1][0] * dp[i - k][0] * getCombi(i - 1, k - 1);
            }
        }
    }
    while (t--) {
        cin >> n; cout << dp[n][0] + dp[n][1] << "\n";
    }

    return 0;
}

결과

• 설명하기가 좀 쉽지않다. 생각날때마다 더 다듬어야겠다.