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

문제 링크: https://www.acmicpc.net/problem/2133

2133번: 타일 채우기

 

1. 문제 풀이
그림을 참조하시면 될 것 같습니다.

​

 

 

 

 

 

    n = int(input())

    dp = [0 for _ in range(31)]
    dp[0] = 1

    for i in range(2, n+1, 2): #n이 짝수 일때만 고려하면 되므로 2에서 시작해서 2씩 늘린다
        dp[i] = dp[i-2] * 3 #바로 전 단계 dp에서는 x3 이지만,
        for j in range(0, i-2, 2): #나머지 단계의 dp들에서는 x2를 해주고 더해주면 된다.
            dp[i] += dp[j] * 2

    print(dp[n])