증가-팬린드롬
문제
양의 정수의 수열이 주어질 때 앞으로 읽던 뒤로 읽던 같은 수열이면 “팰린드롬“이라고 한다.
예를 들어, 두 수열은 “팰린드롬” 이다.
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
“팰린드롬” 수열 중 중간 위치에 있는 수까지 감소하지 않는 수열은 “증가-팰린드롬”이라고 한다.
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 => “증가-팰린드롬”이다.
양의 정수 N이 주어질 때 수열의 합이 N이 되는 “증가-팰린드롬”의 개수를 구하라.
주어지는 입력의 경우의 수는 64 비트 정수로 표현이 가능하다.
몇가지 보기를 보면,
1: (1)
2: (2), (1 1)
3: (1 1 1)
4: (4), (1 2 1), (2 2), (1 1 1 1)
5: (5), (1 3 1), (1 1 1 1 1)
6: (6), (1 4 1), (2 2 2), (1 1 2 1 1), (3 3), (1 2 2 1), (1 1 1 1 1 1)
