[BOJ] 2133번 - 타일 채우기

---

문제설명

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

2133번: 타일 채우기

사고과정

• 개인적으로 너무 어려웠다. 간단하다고 생각했는데, 타일과 주어진 틀의 세로길이가 딱맞아떨어지지 않다 보니까 추가로 생기는 경우의 수를 어떻게 해야 할지 몰랐다..
• 구글링을 해보니 다른 분의 좋은 풀이를 참고해서 풀었다. 핵심은 '가로 길이가 2인 타일'에 포커스를 맞춰서 점화식을 세우는 것인데, 가로 길이가 2, 4, 6, ..., $i$(2의 배수일 때)인 경우를 매번 고려해야 한다.
• 잘 이해가 안간다면 여기 풀이를 참고하자..! 그림을 그려주신 풀이도 있다!(감사합니다)

풀이(스스로 못 푼 풀이)

n = int(input())
if n == 1:
    print(0)
else:
    dp = [0] * (n + 1)
    dp[2] = 3
    for i in range(4, n+1, 2):
        dp[i] = dp[i-2] * 3 + sum(dp[:i-2]) * 2 + 2  # +2는 전체 i 길이 가로의 타일 사용
    print(dp[n])