BOJ-2705 팰린드롬 파티션

필요한 지식

1. 동적계획법

접근

• 왼쪽 절반과 오른쪽 절반이 재귀적인 팰린드롬이거나 비어있을때의 경우의 수를 구해줘야한다.

• n이 7인경우 경우의 수는 아래와 같다.

1 1 1 1 1 1 1
    3 1 3
  1 1 3 1 1
    2 3 2
    1 5 1
      7

• n의 재귀적인 팰린드롬 파티션에서 정가운데에 오는 숫자가 i 일때 양 옆으로 올수 있는 재귀적인 팰린드롬은 (n-i/2)의 재귀적인 팰린드롬 파티션 개수와 일치한다.

• n의 재귀적인 팰린드롬 파티션의 개수는 i가 0부터 n까지 (n-i/2)의 재귀적인 팰린드롬 파티션개수의 합이다.

코드(C++)

#include <iostream>
#include <string.h>
using namespace std;
int dp[1001];
int go(int n) {
	int& ret = dp[n];
	if (ret != -1) return ret;
	ret = 0;
	for (int i = 0; i < n; ++i) {
		if (((n - i) / 2) * 2 + i == n) ret += go((n - i) / 2);
	}
	return ret += 1;
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t; cin >> t;
	memset(dp, -1, sizeof(dp));
	dp[0] = 0; dp[1] = 1; dp[2] = dp[3] = 2;
	while (t--) {
		int n; cin >> n;
		cout << go(n) << "\n";
	}
}

결과