시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 855 | 591 | 425 | 74.301% |
양의 정수 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의 재귀적인 팰린드롬 파티션의 개수를 출력한다.
3 4 7 20
4 6 60