[ Lv 4 ] [ DP ] 3 x n 타일링

https://programmers.co.kr/learn/courses/30/lessons/12902

코딩테스트 연습 - 3 x n 타일링

---

풀이 과정

---

1. DP 테이블을 구성한다.

2. 현재 위치 i 기준으로 가능한 경우의 수

   • i-2칸을 채우는 경우의 수에서 2칸 채우는 경우의 수인 3을 곱한다.
   • i-4칸을 채우는 경우의 수에서 4칸 채우는 경우의 수인 2를 곱한다.
     • 4칸 채우는 경우의 수에서.. 가운데에 블록 하나씩 넣으면 2칸씩 늘어난다.
     • 6칸 채우는 경우의 수도 2개, 8칸 채우는 경우의 수도 2개, ..
     • 각각을 처리해 주어야 한다.

3. 테이블을 채우기 전, 계산한 결과를 1,000,000,007으로 나눈 나머지를 저장해 둔다.

4. dp[n]을 리턴해주면 된다.

---

소스 코드

---

def solution(n):
    answer = 0
    dp = [1] + [0] * (n)

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

        dp[i] = dp[i] % 1000000007
    answer = dp[n]
    return answer