[백준]2133 타일채우기 #3*N타일

난 이 문제가 너무어렵다. 이전에 저장한 캐시를 쓰긴 하지만 계속해서 새로운것이 추가되는 형태의 dp문제는 처음이라 너무 어렵다.

​

1. 풀이

 (1) i가 홀수이면 만들 수 있는 경우가 없으므로 0

 (2) 짝수일때는 아래의 두가지 경우를 합해준다

  ① i-2일때 만들 수 있는 경우에 세가지 서로다른 형태를 추가한 경우 dp[i-2]*3

  ② i-2에서 추가한것만으론 만들 수 없는 형태 (2칸씩 쪼개지지 않는 경우) <=> 매번 새롭게 만들어지는 형태

​

2. 소스코드

N=int(input())
dp=[0 for i in range(N+1)]
dp[0]=1

for i in range(2,N+1):
    if i%2!=0:
        continue
    dp[i]+=dp[i-2]*3
    for j in range(4,i+1,2):
        dp[i]+=dp[i-j]*2

print(dp[N])