BOJ 3948, 홍준이의 친위대
ProblemSolving ·이 문제는 DP문제입니다.
풀이
양쪽 끝에 애들은 상관없이 가운데 애들이 양옆이 자기보다 크거나 작아야한다.
처음 가진 수보다 다음 수가 크고 그 다음은 작고 혹은 처음 가진 수보다 다음 수가 작고 그 다음은 크고 를 반복적으로 시행하면 되는 것 같다.
결국 높았다 낮아졌다 높았다 낮아졌다 혹은 낮았다 높아졌다 낮아졌다 높아졌다 의 경우의 수 인 것이다.
지그재그 서기 라는 문제와 유사하다고 한다.
나같은 경우에는 dp[현재 위치][현재의 수][커져야하는지 작아져야하는지(1 or 0)] 로 식을 세워서 재귀적으로 dp를 풀어냈다.
size가 0일때는 현재의 수보다 큰 것들로만, size가 1일때는 현재의 수보다 작은 것들로만 포문을 돌려서 재귀탐색하였다.
현재의 위치(depth)가 n이 될 때 return 1을 하여 모든 경우의 수를 구했다.
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
using namespace std;
typedef long long ll;
ll t, n, ans, dp[21][21][2], chk[21];
ll go(ll depth, ll now, ll size)
{
if (depth == n)
return 1;
ll &ret = dp[depth][now][size];
if (ret != -1) return ret;
ret = 0;
if (size == 0)
for (int i = now + 1; i <= n; i++)
if(chk[i]==0)
chk[i]=1,ret += go(depth + 1, i, 1),chk[i]=0;
if (size == 1)
for (int i = now - 1; i >= 1; i--)
if (chk[i] == 0)
chk[i]=1,ret += go(depth + 1, i, 0),chk[i]=0;
return ret;
}
int main()
{
scanf("%lld", &t);
while (t--)
{
ans = 0;
scanf("%lld", &n);
memset(dp, -1, sizeof(dp));
memset(chk, 0, sizeof(chk));
if (n == 1)
{
printf("1\n");
continue;
}
for (ll i = 1; i <= n; i++)
{
chk[i] = 1;
ans += go(1, i, 0);
ans += go(1, i, 1);
chk[i] = 0;
}
printf("%lld\n", ans);
}
return 0;
}