[백준] 3948: 홍준이의 친위대

0. 문제 주소

 

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

3948번: 홍준이의 친위대

 

 

1. 풀이

 

처음엔 1차원 dp 배열로 점화식을 세워보려고 했으나 실패했다.

 

탑다운으로 현재 위치에 서려는 사람 기준 남아있는 사람들 중에 이 사람보다 키가 작은 사람 / 큰 사람의 수와 함께

 

다음에는 이 사람보다 큰 사람이 와야 하는지 여부를 파라미터로 사용한다.

 

 

2. 풀이 코드

 

* 유의할 점

 

#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll dp[22][22][2];

ll solve(int L, int R, bool getting_higher){
	if (L + R == 0) return 1;
	ll &ret = dp[L][R][getting_higher];
	if (ret != -1) return ret;
	ret = 0;
	
	if (!getting_higher){ // choose L
		for (int next=0;next<L;next++){ 
			// .....curr.....
			// <-L->    <-R->
			// ..next...curr.....
			// choose next in L
			ret += solve(next, (L+R) - (next+1), 1);
		}
	}
	else{
		for (int next=0;next<R;next++){
			// .....curr.....
			// <-L->    <-R->
			// .....curr..next...
			// choose next in R
			ret += solve((L+R) - (next+1), next, 0);
		}
	}
	return ret;
}

int main(){
	#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	#endif

	// ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	memset(dp, -1, sizeof(dp));
	
	int t;
	scanf("%d", &t);
	while(t--){
		int n;
		scanf("%d", &n);
		if (n == 1) {
			printf("1\n");
			continue;
		}
		ll ans = 0;
		for (int i=0;i<n;i++){
			ans += solve(i, n - (i+1), 0);
			ans += solve(i, n - (i+1), 1);
		}
		printf("%lld\n", ans);
	}
	
	return 0;
}