[백준 파이썬] 2133 타일 채우기

2133번: 타일 채우기

 

문제



주어진 타일을 이용해서 타일을 완성시키는 경우의 수를 출력하는 문제이다.

---

풀이

먼저 타일을 배치할 수 있는 경우의 수를 구해야한다.

n이 홀수일 경우 타일을 배치할 칸이 부족하므로 경우의 수가 0이된다.

 

n = 2 의 경우는 다음과 같다.

 

n = 4 의 경우 고유한 모양 2개 + n = 2일 때의 모양의 조합 9가지 = 11가지가 된다.

 

n = 6 의 경우 끝부분의 n이 2, 4, 6인 경우를 모두 더해주면 된다.

이 때 6인경우는 고유패턴 2가지이므로 2를 더해주면 된다.

이런식으로 짝수의 경우를 모두 표현할 수 있다.

 

해당 식을 그림으로 나타내면 다음과 같다.

 

 

코드로 나타내면 다음과 같다.

dp[i] = dp[i - 2] * 3 + sum(dp[:i-2]) * 2 + 2

 

 

 

코드

N = int(input())

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


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

print(dp[N])