[코테] 백준 다이나믹 프로그래밍 2133번 문제

2133번 : 타일 채우기

문제 링크

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

문제 설명

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

입력

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

출력

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

문제풀이

나도 고민하다가 결국에는 검색을 통해서 해결했다.

1. 홀수일 때는 2x1, 1x2 타일로 다 채울수 없기에 0을 출력
2. 짝수일 때는 (바로 직전 짝수 타일수의 * 3 + 2) + (보다 더 전의 짝수 타일들의 * 2)를 합한 값이다.

N = int(input())
dp = [0] * 31
dp[2] = 3

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

    for j in range(i-4, -1, -2) :
        dp[i] += dp[j] * 2

print(dp[N])