홍준이의 친위대

Problem link: https://www.acmicpc.net/problem/3948

은근히 고민을 많이하게 만든 문제였는데, 답은 의외로 간단한 DP로 풀어줄 수 있다.

문제를 곰곰히 생각해보면, 서로 다른 키를 갖는 N명이 있을 때 이들을 지그재그 형태로 배치하는 경우의 수를 헤아리는 것과 같다.

이러한 지그재그 배치는 아래와 같이 두 종류가 있을 수 있다.

• 큰작으로 시작하는 경우: 3/1/2, 2/1/3, 4/1/3/2, 4/2/3/1 등
• 작큰으로 시작하는 경우: 1/2, 1/3/2 등

이제, i-1명의 서로 다른 병사가 큰작 또는 작큰으로 배치되는 경우의 수를 이미 모두 다 헤아려 놓았다고 가정하자.

i번째 병사가 추가될 때(단, i번째 병사는 모든 병사들 중 키가 가장 큼), i번째 병사의 좌우에 병사들을 배치해보자.

• 만약, i번째 병사의 왼쪽에 홀수명의 병사를 배치한다고 해보자.

• i번째 병사가 병사들 중 키가 가장 크므로, i번째 병사 왼쪽에는 무조건 작큰으로 시작하는 배치가 올 수 밖에 없다.
  (e.g. 작->큰->작->i번 병사)

• i번째 병사의 오른쪽은 홀수명 짝수명에 관계 없이 무조건 작큰으로 시작하는 배치가 와야한다.
  (e.g. i번 병사->작->큰->작)

• 비슷하게, i번째 병사의 오른쪽에 짝수명의 병사가 배치되는 경우에는,

• i번째 병사 왼쪽에는 큰작으로 시작하는 배치가 오고,

• 오른쪽에는 작큰으로 시작하는 배치가 온다.

따라서, 아래와 같이 점화식을 세워줄 수 있다.

• 작큰[n]: 서로 키가 다른 n명을 규칙에 따라 배치할 때, 작큰으로 시작하는 경우의 수

• 큰작[n]: 서로 키가 다른 n명을 규칙에 따라 배치할 때, 큰작으로 시작하는 경우의 수

• C(n, r): nCr, n명 중 r명을 고르는 경우의 수, i번째 병사 왼쪽에 올 병사를 고르는 데에 쓰임

• 작큰[n]: C(n, 1) 작큰[1] 작큰[n-2] + C(n, 3) 작큰[3] 작큰[n-4] + ...

• 큰작[n]: C(n, 0) 큰작[0] 작큰[n-1] + C(n, 2) 큰작[2] 작큰[n-3] + ...

위의 점화식에서 덧셈으로 연결된 각 항의 3개 인수는 아래와 같이 이해할 수 있다.

• i번 병사 왼쪽에 갈 병사들을 고르고,
• 고른 병사들이 왼편에 배치될 때의 경우의 수를 구한 뒤,
• 남은 병사들이 오른편에 배치되는 경우의 수를 구한다.

#include <iostream>
#include <cstdint>

using namespace std;

const int kMaxN = 20;

int N;
int64_t CACHE[2][kMaxN + 1];

int64_t nCr[kMaxN + 1][kMaxN + 1];

void Initialize(void)
{
  for (int n = 0; n <= kMaxN; ++n)
  {
    nCr[n][0] = 1;
  }

  for (int n = 1; n <= kMaxN; ++n)
  {
    for (int r = 1; r <= n; ++r)
    {
      nCr[n][r] = nCr[n - 1][r] + nCr[n - 1][r - 1];
    }
  }
}

int64_t Solve(const int type, const int n)
{
  if (n <= 1)
  {
    return 1;
  }

  int64_t& ret = CACHE[type][n];

  if (ret != -1)
  {
    return ret;
  }

  ret = 0;
  for (int left = type; left < n; left += 2)
  {
    int right = n - left - 1;
    ret += Solve(type, left) * nCr[n - 1][left] * Solve(1, right);
  }

  return ret;
}

int main(void)
{
  // For Faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  // Initialize
  Initialize();
  for (int i = 0; i < kMaxN + 1; ++i)
  {
    CACHE[0][i] = -1;
    CACHE[1][i] = -1;
  }

  // Read Input
  int tc;
  cin >> tc;
  while (tc--)
  {
    cin >> N;

    // Solve
    if (N == 1)
    {
      cout << 1 << '\n';
    }
    else
    {
      cout << Solve(0, N) + Solve(1, N) << '\n';
    }
  }

  return 0;
}