[백준/BOJ] gold4 - 2133번 타일 채우기 (Python)

▶2133 - 타일 채우기

▶문제

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

 

▶입력

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

 

▶출력

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

 

▶예제

 

▶힌트

아래 그림은 3×12 벽을 타일로 채운 예시이다.

▶풀이

dp를 이용해서 푸는 문제이다.

N이 홀수일 때는 짝이 맞지 않기 때문에 항상 0이 된다.

그럼 N이 짝수일 때만 생각해주면 된다.

2, 4, 6일 때 규칙이 어떻게 되는지 가장 먼저 생각해주었다.

n = int(input())

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

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