[Python] 백준 2133번 - 타일 채우기 (골드 4)

혼자 힘으로 풀었는가? X

알고리즘 분류
 - DP

 

문제

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

입력

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

출력

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

 

---

 

문제를 읽지도 않고 제목만 보자마자 DP인걸 알아야 한다

 

이제 문제는 점화식을 어떻게 정립하는가? 이다.

 

https://blog.naver.com/zdudmanz/222285104463

Python 백준 2133 타일채우기

 

점화식은 다음과 같다.

 

 

예를 들어 dp[n]을 구하고자 한다면

 

dp[8] = dp[6] * dp[2] -> dp[6]에 2칸 추가한 경우의수

         + dp[4] * 2 -> dp[4] -> 크기가 n-4부터 2까지의 경우의 수에 새로운 모양의 타일을 추가한 경우의 수

         + dp[2] * 2

         + dp[0] * 2 -> 초기값 1 * 2 = 2 

 

import sys

input = sys.stdin.readline

n = int(input())

if n % 2 != 0:
    print(0)
else:
    dp = [0] * (n+1)
    dp[0] = 1 # 기본값
    for i in range(2, n + 1, 2):
        dp[i] = dp[i - 2] * 3  # 가로로 2개의 타일 추가하는 경우, 3 = dp[2]
        
        for j in range(4, i + 1, 2):
            dp[i] += dp[i - j] * 2  # 다른 모양의 타일을 추가하는 경우
            
    print(dp[n])

 

아마 이 문제가 코딩테스트로 나온다면 풀 자신이 없다...

 

예제에 n = 2 일대 결과 3 뿐이어서

 

n = 4, n =6의 경우의 수를 직접 그러야하는데... 쉬울줄 알았는데 어려운 문제였다.