[백준] 2133번: 타일 채우기 - [Python/파이썬]

문제

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

2133번: 타일 채우기

 

 

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

입력

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

출력

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

코드

import sys
input=sys.stdin.readline

n=int(input())
dp=[0 for _ in range(31)]
dp[2]=3
for i in range(4,n+1,2):
    dp[i]=3*dp[i-2]+(sum(dp[:i-2])+1)*2

print(dp[n])

문제 해결

https://kosaf04pyh.tistory.com/236

[알고리즘 문제] 백준2133 - 타일 채우기

이 풀이를 보고 점화식을 세워 DP로 풀이하였다. (풀이 참조: https://kosaf04pyh.tistory.com/236)

F[N] = ( F[N - 2] * 3 ) + ( F[N - 4] * 2 ) + ( F[N - 6] * 2) + ( F[N - 8] * 2 ) + ... + ( F[0] * 2 )