단봉 회문 분할

시간 제한1초메모리 제한128 MB

요약

값이 가운데까지 커졌다가 다시 작아지는 팰린드롬 수열의 합으로 N을 나타내는 방법의 수를 구한다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 조합론, 수학, 구현
정답자: 아직 제출이 없습니다

문제

양의 정수로 이루어진 수열을 앞에서 읽으나 뒤에서 읽으나 같으면, 그 수열을 회문(palindrome) 이라고 합니다. 예를 들면 다음과 같습니다.

23 11 15 1 37 37 1 15 11 23
1 1 2 3 4 7 7 10 7 7 4 3 2 1 1

회문 수열의 값이 가운데 값까지 줄어들지 않고(비내림차순), 이어서 (회문이므로) 가운데부터 끝까지 늘어나지 않으면(비오름차순), 그 수열을 단봉 회문(unimodal palindrome) 이라고 합니다. 예를 들어 위의 첫 번째 수열은 단봉 회문이 아니지만, 두 번째 수열은 단봉 회문입니다.

단봉 회문 수열에 속한 정수의 합이 $N$ 이면, 그 수열을 정수 $N$ 의 단봉 회문 분할(unimodal palindromic decomposition) 이라고 합니다. 예를 들어 처음 몇 개의 정수에 대한 단봉 회문 분할은 다음과 같습니다.

(1)
(2), (1 1)
(3), (1 1 1)
(4), (1 2 1), (2 2), (1 1 1 1)
(5), (1 3 1), (1 1 1 1 1)
(6), (1 4 1), (2 2 2), (1 1 2 1 1), (3 3), (1 2 2 1), (1 1 1 1 1 1)
(7), (1 5 1), (2 3 2), (1 1 3 1 1), (1 1 1 1 1 1 1)
(8), (1 6 1), (2 4 2), (1 1 4 1 1), (1 2 2 2 1), (1 1 1 2 1 1 1), (4 4), (1 3 3 1), (2 2 2 2), (1 1 2 2 1 1), (1 1 1 1 1 1 1 1)

정수 $N$ 이 주어졌을 때, 그 수의 단봉 회문 분할의 개수를 구하는 프로그램을 작성하세요.

입력

입력은 한 줄에 하나씩 주어지는 양의 정수들로 이루어집니다. 0 만 적힌 줄은 입력의 끝을 뜻하며, 처리하지 않습니다.

출력

마지막의 0 을 제외한 각 입력 값마다, 그 값과 공백 하나, 그리고 그 값의 단봉 회문 분할의 개수를 한 줄에 출력합니다.

제한

$1 \le N \le 250$

예제3

예제 1

입력

예상 출력

2 2
3 2
4 4
5 3
6 7
7 5
8 11
10 17
23 104
24 199
131 5010688
213 1055852590
92 331143

예제 2
입력
```
1
0
```
예상 출력
```
1 1
```
예제 3
입력
```
1
2
3
0
```
예상 출력
```
1 1
2 2
3 2
```