백준2133(파이썬) - 타일 채우기

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

2133번: 타일 채우기

• 이 문제를 읽고 처음 든 생각은 'DP로 풀어야겠다. Bottom-up으로 풀어야겠다' 였다.
• 그리고 n이 짝수일 때 만 다 채울 수가 있다.
• n에 대해서 n-2 까지의 dp 값에 가로길이 2 짜리 타일로 만들수 있는 3가지 경우를 곱한 경우
• dp[n-2] * 3
• n에 대해서 가로 길이 n짜리의 새로운 타일 덩어리를 만드는 2가지 경우
• 2
• n에 대해서 0 ~ n-4 까지의 타일 뒤에 자신을 붙혀서 만들 수 있는 2가지 경우를 곱한 경우
• ( dp[0] + dp[2] + ... dp[n-4] ) * 2

위에 3개의 식을 다 더한 것이 dp[n] 이 된다.

 

import sys
input = sys.stdin.readline

n = int(input())

dp = [0]*(n+2)

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

print(dp[n])
#100 436252889