[Programmers] Level 2. 3xn 타일링

🔗 Problem Link

프로그래머스

---

❔Thinking

• 2x1 타일로, 가로가 n이고 세로가 3인 공간을 채우는 방법의 수를 반환한다.
• 답을 1,000,000,007으로 나눈 나머지를 반환해야 한다.

---

💻Solution

def solution(n):
    if n % 2 != 0:
        return 0
    dp = [0, 0, 3, 0, 11] + [0 for _ in range(n-3)]
    for i in range(5, n+1):
        if i % 2 == 0:
            dp[i] += dp[i-2] * 3 + 2
            for j in range(i-4, -1, -2):
                dp[i] += dp[j] * 2
            dp[i] = dp[i] % 1000000007
    return dp[n]

---

🗝️keypoint

1. 세로가 3이기 때문에, n이 홀수인 경우에는 2x1 타일로 채울 수 없다.
2. dp 문제로, 점화식을 세워 문제를 해결해야 한다.
   1. n이 2일 경우, 총 3가지 방법이 있다.
   2. n이 4일 경우, 총 11가지 방법이 있다.
   3. n이 6일 경우, 총 41가지 방법이 있다.
   4. 즉, n-2의 경우에 옆에 3가지를 붙일 수 있고, n-4, n-6 ...2까지 양 옆을 1로 하고 가운데를 나머지로 하는 모양이 각 2개씩 가능하다. 따라서 점화식은 다음과 같이 세울 수 있다.
   5. f(n) = f(n-2) * 3 + (f(n-4) + f(n-6) + ... + f(2)) * 2 + 2