재귀적 회문 timer 1s memory 64MB

임의의 자연수 N 은 다음 처럼 여러개의 자연수 수열의 합으로 나타낼 수 있다:

15 = 1 + 2 + 3 + 4 + 5 = 1 + 2 + 1 + 7 + 1 + 2 + 1

첫번째 예제는 (1, 2, 3, 4, 5) 라는 수열의 합이며, 두번째 예제는 (1, 2, 1, 7, 1, 2, 1)의 수열의 합이다.

앞에서부터 읽는 것과 뒤에서 부터 읽는 것이 같을 경우 이를 회문이라 한다. 위의 예에서 첫번째 조합은 회문이 아니며, 두번째의 경우에는 회문이라 할 수 있다.

수열이 있을 때 수열을 절반으로 나눴을 때 왼쪽 부분이 회문이고, 또 나눈부분의 절반이 회문이고, 이러한 조건을 계속 만족하며 절반이 하나이거나 0일 경우 이를 재귀적 회문이라고 한다. 여기서 절반이란 M개의 숫자가 있을 때, 앞 부분의 floor(M/2) 개의 숫자를 뜻한다. 여기서 floor란 소수점이 있을 경우 이를 버린 수를 뜻한다. 예를 들어 floor(4.5)일 경우 4가 된다.

임의의 자연수 N에 대해 수열의 모든 원소의 합이 N이고, 재귀적인 회문을 이루는 수열의 개수가 몇인지 찾는 프로그램을 작성하라.

예를 들어 N = 7 일 경우 재귀적 회문의 예는 다음과 같다.

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