2133번 파이썬

이 문제는 홀수 일때는 경우의 수가 존재하지 않아서 짝수일때만 확인해주면 된다.

처음에 2일때 경우의 수는 3개이고

4개일때부터는 p[2]*p[2] + 2이다  뒤에 두가지는 다음과 같은 모양이다

이 모양 하나와 반대 모양 총 두가지이다

즉 p[4] = p[2]*p[2] + 2 이다.

6일 경우부터는 경우가 (2,2,2) (4,2) (2,4) (6)인데

앞에 (2,2,2) (4,2) 이 둘은 p[4]*p[2]한 값과 같고 

(2,4)는 4의 모양중 전체 가로길이가 4인 두가지 모양의 경우만 계산해주면 된다.(나머지 경유는 앞에 4,2와 동일하기 때문)

즉 p[2]*2이다.

그리고 마지막으로 가로길이가 6인 경우만 계산해주면된다. 가로길이가 6인 경우는

와 반대 모양 총 두가지이다.

8도 마찬가지로 이렇게 반복되고 이걸 식으로 나타내면

p[n] = p[n-2]*p[2] + p[n-4]*2+p[n-6]*2+..p[0]*2로 나타낼 수 있다.

이걸 코드로 나타내면 다음과 같이 나타낼 수 있다.

import sys
input = sys.stdin.readline
n = int(input())
p=[0 for _ in range(n+1)]
p[0]=1
for num in range(2,n+1,2):
  p[num] = p[num-2]*3
  for idx in range(0,num-2,2):
    p[num]+=p[idx]*2

print(p[n])