2705 백준 파이썬

회문구조이면서 재귀구조를 가지는 팰린드롬 파티션의 갯수를 찾는 문제

 

예를들어  7은

7

1+5+1

2+3+2

1+1+3+1+1

3+1+3

1+1+1+1+1+1+1

은 되나, 1+2+1+2+1은 안된다. 1+2와 2+1이 재귀가 아니기 때문이다.

 

규칙을 찾아보자.

 

중간수를 기준으로 n을 나눠볼 수 있는데, 5와 6의 예시로 살펴보자.

5의 경우	6의 경우
1이 중간에 오는 경우, 1+1+1+1+1 2+1+22가 중간에 오는 경우, 없음 3이 중간에 오는 경우, 1+3+1 4가 중간에 오는 경우, 없음 5가 중간에 오는 경우 5	1이 중간에(?) 오는 경우, 1+1+1+1+1+1 2가 중간에 오는 경우, 2+2+2 1+1+2+1+1 3이 중간에(?) 오는 경우, 3+3 4가 중간에 오는 경우, 1+4+1 5가 중간에 오는 경우, 없음 6이 중간에 오는 경우, 6

 

그런데 여기서 기준수를 제외하고 생각해보면 사실 이렇게 된다.

 

5	6
1이 중간에 오는 경우, n(2)+기준수+n(2) 2가 중간에 오는 경우, 없음 3이 중간에 오는 경우, n(1)+기준수+n(1) 4가 중간에 오는 경우, 없음 5가 중간에 오는 경우, 1	1이 중간에(?) 오는 경우, 1 2가 중간에 오는 경우, n(2)+기준수+n(2) 3이 중간에(?) 오는 경우, 1 4가 중간에 오는 경우, n(1)+기준수+n(1) 5가 중간에 오는 경우, 없음 6이 중간에 오는 경우, 1
계 : 4	계 : 6

 

이와 같은 것을 몇번 해보면 알겠지만, 이걸 통해 알 수 있는 것은 

 

1. n(짝수)=n(홀수)+2이다.

2. n(홀수)=n((현재차수-1)//2)+....+n(1)까지의 합+1이다.

이다.

 

그리고 2번 사실에서,

n(5)=n(2)+n(1)+1인데, n(7)=n(3)+n(2)+n(1)+1이므로,

n(7)=n(5)+n(3)으로 요약할수 있다.

 

이것을 일반화하면

 

홀수의 경우,

n(k)=n((k-1)//2)+n(k-2)로

 

짝수의 경우

n(k)=n(k-1)+2로

 

요약 할 수 있다.

 

따라서 코드를 작성하면,

t=int(input())
dp=[1,2,2,4,4]
for _ in range(t):
    n=int(input())
    if n<=len(dp):
        print(dp[n-1])
    else:
        for x in range(len(dp),n):
            if x//2:
                dp.append(dp[(x-1)//2]+dp[x-2])
            else:
                dp.append(dp[x-1]+2)
        print(dp[n-1])