취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2705번 문제인 팰린드롬 파티션이다.
문제는 아래 링크를 확인하자.

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

합이 N인 팰린드롬 파티션은 그 길이가 홀수인 경우 가운데에 수 하나와 그 양옆으로 두 같은 팰린드롬 파티션이, 짝수인 경우 두 같은 팰린드롬 파티션이 연달아 써져있는 형태로 나타나는 점을 관찰하자.

위의 관찰을 이용하면, 가운데에 수 하나를 정한 홀수 길이의 팰린드롬 파티션의 개수는 N에서 정한 수를 빼고 남은 수(짝수여야한다)의 절반을 총합으로 하는 팰린드롬 파티션의 수와 같고, 짝수길이의 팰린드롬 파티션의 개수는 N(짝수여야한다)의 절반을 총합으로 하는 팰린드롬 파티션의 수와 같아야 함을 알 수 있다.

위의 관찰을 기반으로 memoization을 화룡하는 재귀를 통해 문제를 해결하자. 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

int T;
ll dp[1001];
bool visited[1001];

ll func(int N) {
	if (visited[N]) return dp[N];
	visited[N] = 1;

	ll& ret = dp[N];
	for (int i = 1; i < N; i++) { // 홀수길이 팰린드롬
		int nxt = N - i;
		if (nxt & 1) continue;
		ret += func(nxt >> 1);
	}
	if (!(N & 1)) ret += func(N >> 1); // 짝수길이 팰린드롬

	ret++;
	return ret;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> T;
	while (T--) {
		int x; cin >> x;
		cout << func(x) << '\n';
	}
}