항해99 리부트코스 알고리즘 1주 - 3일차 팰린드롬 파티션

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

 

팰린드롬 파티션 다국어

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

953

658

475

73.643%

문제

양의 정수 N의 파티션은 합이 N이 되는 수열을 말한다. 보통 숫자 사이에 +를 넣어서 나타낸다. 예를 들면

15 = 1+2+3+4+5 = 1+2+1+7+1+2+1 이다.

어떤 파티션을 앞에서 읽을 때와 뒤에서 읽을 때가 같으면 이 파티션을 팰린드롬 파티션이라고 한다. 위의 예에서 첫 번째 파티션은 팰린드롬 파티션이 아니지만, 두 번째 파티션은 팰린드롬 파티션이다.

어떤 파티션이 m개의 정수로 이루어져 있다면, 왼쪽 절반은 처음 floor(m/2)개의 원소, 오른쪽 절반은 마지막 floor(m/2)개의 원소이다. 

재귀적인 팰린드롬 파티션은 어떤 파티션이 팰린드롬이면서, 왼쪽 절반과 오른쪽 절반이 재귀적인 팰린드롬이거나, 비어있을 때 이다. 모든 정수는 적어도 2개의 재귀적인 팰린드롬 파티션을 항상 갖는다. (n과, 1 n개) 

7의 재귀적인 팰린드롬 파티션은 다음과 같이 6가지가 있다.

7, 1+5+1, 2+3+2, 1+1+3+1+1, 3+1+3, 1+1+1+1+1+1+1

어떤 수 N을 입력받은 다음에, 재귀적인 팰린드롬 파티션의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T(1 <= T <= 1,000)가 주어진다. 각 테스트 케이스는 양의 정수 1개로 이루어져있고, 이 수가 문제에서 설명한 N이고, 1,000보다 작거나 같다.

출력

각 테스트 케이스에 대해 한 줄에 하나씩 N의 재귀적인 팰린드롬 파티션의 개수를 출력한다.

예제 입력 1 복사

3
4
7
20

예제 출력 1 복사

4
6
60