#204 백준 파이썬 [2133] 타일 채우기 - 점화식

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

 

#Solution

규칙을 찾는 데 꽤 애먹은 도형이다.

1) 홀수 번째는 만들 수 없다. 따라서 0

2) 짝수 번째는 이전에 만든 것들에 영향을 받는다.

3) 2,4,6,8,10... 이 순서로 간다고 했을 때,

 

n = <바로 이전 항> (n-2) * 3

+ <첫항 ~ 더이전 항> (n ~ n-4) * 2

+ <자기 자신만 만들 수 있는 도형> 2

 

도형을 그리다보면 최댓값일 때 자기 자신만이 가질 수 있는 도형이 무엇인지 알 수 있다. 대충 양옆에 하나만 서있고 나머지 다 누워있는 도형

def tiles(n):
    answer = [0] * (n + 1)
    if n % 2 == 1:
        return 0
    
    for i in range(2, n + 1, 2):
        if i == 2:
            answer[i] = 3
        else:
            for j in range(2, i, 2):
                if j == i - 2:
                    answer[i] += answer[i-2] * 3 #이전 것은 *3
                    answer[i] += 2 #자기 자신
                else:
                    answer[i] += answer[j] * 2 #그 이전 것들은 *2
                
    return answer[n]

print(tiles(int(input())))