문제 설명
키가 다른 친위대를 배치할 때 키가 지그재그로 배치해야 합니다.
배치할 수 있는 경우의 수를 출력하는 문제입니다.
풀이
이렇게 두 가지 형태로 친위대를 배치할 수 있습니다.
이 중 하나의 경우의 수만 구한 후 x2를 해주면 모든 경우의 수를 할 수 있습니다.
모든 경우의 수를 구하면 TLE이므로 DP 테이블을 만들었습니다.
저는 오른쪽 형태의 경우의 수를 구했습니다.
DP[N 명][X 번째 작은 수] = SUM(DP[N-1][X + 1] ~ DP[N-1][N-1])(N이 홀수)
DP[N 명][X 번째 작은 수] = SUM(DP[N-1][0] ~ DP[N-1][X - 1]) (N이 홀수)
N이 홀수일 때 키가 작아져야 해서 전 사람이 지금 키보다 큰 사람인 경우의 수를 더합니다.
반대로 N이 짝수일 때는 커야 하기 때문에 작은 사람의 경우의 수를 더합니다.
이렇게 DP 테이블을 완성하고 답은 DP[N][0] ~ DP[N][N-1]을 더한 값에 2를 곱한 값을 출력하면 됩니다.
1은 형태가 한 가지이므로 예외 처리를 해줍니다.
소스 코드
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
using namespace std;
int main() {
FIO;
ll dp[25][25] = {};
dp[1][0] = 1;
FOR(i, 2, 20) FOR(j, 0, i - 1) {
int a, b;
if (i & 1) a = j, b = i - 1;
else a = 0, b = j - 1;
FOR(k, a, b) dp[i][j] += dp[i - 1][k];
}
int t; cin >> t; while (t--) {
int n; cin >> n;
ll ans = 0;
FOR(i, 0, n - 1) ans += dp[n][i];
cout << ((n == 1) ? 1 : ans * 2) << '\n';
}
return 0;
}