백준 2133번: 타일 채우기

https://www.acmicpc.net/problem/2133

2133번: 타일 채우기

문제

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

입력

첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.

출력

첫째 줄에 경우의 수를 출력한다.

---

4칸에만 딱 맞춰 넣을 수 있는 타일 구성이 있고.. 6칸에만 딱 맞춰 넣을 수 있는 타일 구성이 있고..

...x칸에만 딱 맞춰 넣을 수 있는 타일이 있다..

는 점이 어질어질하다

 

0. 일단 n이 홀수일 때는 타일을 완성할 수가 없다

for i in range(4,31,2):

1. dp[i]=dp[i-2]*dp[2]

뒤에다가 2칸짜리를 덧붙이는 방법이다. (dp[2]==3)

 

for j in range(0,i-2,2):

2. dp[i]+=dp[j]*2

1번에서는 뒤에다가 2칸짜리를 덧붙였기 때문에..

x칸짜리 타일구성을 뒤에다가 몰아넣ㅇ르수가 없음

x칸짜리 타일구성을 뒤에다가 넣는 방법은.. 

앞에 구성할 경우의수dp[i-x]개 * x칸짜리 타일 방향(위,아래) 두가지 경우..

그래서 dp[j]*2가 되고..

그런거임 

어질어질~

 

n=int(input())

dp=[0]*31
dp[0]=1
dp[1]=0
dp[2]=3
dp[3]=0 #세칸짜리는 못만드네


for i in range(4,n+1,2):
    dp[i]=dp[i-2]*dp[2] #두칸 적은거 + 두칸만큼 뒤에 새로 만들기
    for j in range(0,i-2,2):
        dp[i]+=dp[j]*2 #i칸짜리~i-4칸짜리들이.. 앞에있는경우..
    

print(dp[n])

https://www.youtube.com/watch?v=CJ7C0wQVxCI 

이 유튜브 참고해서 공부했더니 좀 이해함..