재귀적 팰린드롬 파티션
시간 제한1초메모리 제한128 MB
정수 N에 대해 팰린드롬이면서 좌우 절반도 재귀적으로 팰린드롬 분할이 되는 분할의 개수를 구합니다.
문제
양의 정수 N의 파티션은 양의 정수로 이루어진 수열이며, 모든 원소의 합이 N인 것이다. 보통 각 원소 사이에 +를 넣어 나타낸다.
파티션을 앞에서 읽은 순서와 뒤에서 읽은 순서가 같으면 팰린드롬 파티션이라고 한다.
길이가 m인 파티션에서 왼쪽 절반은 처음 floor(m / 2)개의 원소이고, 오른쪽 절반은 마지막 floor(m / 2)개의 원소이다. 길이가 홀수이면 가운데 원소는 어느 절반에도 포함되지 않는다.
재귀적인 팰린드롬 파티션은 다음 조건을 만족하는 파티션이다.
- 전체 파티션이 팰린드롬이다.
- 왼쪽 절반과 오른쪽 절반이 비어 있거나, 각각 재귀적인 팰린드롬 파티션이다.
N 자체로 이루어진 파티션과 1을 N개 나열한 파티션은 항상 조건을 만족한다. 양의 정수 N이 주어질 때, N의 재귀적인 팰린드롬 파티션 개수를 구하라.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. (1 <= T <= 1,000)
다음 T개의 줄에는 양의 정수 N이 하나씩 주어진다. (1 <= N <= 1,000)
출력
각 테스트 케이스마다 N의 재귀적인 팰린드롬 파티션 개수를 한 줄에 하나씩 출력한다.