[python] 백준 2133 : 타일 채우기

문제

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

2133번: 타일 채우기

 

문제 풀이

사실은 못풀었다! ^___^

처음에 2x1, 1x2 타일로 3xN 의 타일을 채우는 경우의 수를 생각해 봤는데...

이렇게 5개가 있을 거라고 생각했다.

그래서 N이 2인 형태가 3개. 4인 형태가 2개라고 생각해서

점화식이 dp[n] = dp[n-2] *3 + dp[n-4] *2 일거라고 생각했다.

N= int(input())

dp=[0]*31
dp[2] = 3
dp[4] = 11

for i in range(5,N+1):
    dp[i] = dp[i-2] *3 +dp[i-4] *2
print(dp)

그런데 이렇게 푸니깐 틀렸다 ^___^

그래서 테스트 케이스를 확인해 보니깐 dp[6] = 41이였다.

위의 점화식으로 dp[6]을 계산해보면 39이고, 2가 부족하다.

 

그래서 3x6의 형태가 2개 있는 것 같다고 생각했고,

dp[n] = dp[n-2] *3 + dp[n-4] *2 + dp[n-6] *2 을 추가했는데도 틀렸다!

 

결국 잘 모르겠어서 풀이를 찾아봤는데..

n=6부터는 아래 그림처럼 3xN의 형태를 2개씩 계속 만들 수 있다.

따라서 점화식은

이 될 것이다.

 

N이 늘어날 때마다 새로운 형태가 생길 거라는 생각을 못해서

풀지 못했던 것 같다..