[Gold IV] 타일 채우기 3 - 14852

문제 링크

성능 요약

메모리: 258724 KB, 시간: 2388 ms

분류

다이나믹 프로그래밍

문제 설명

2×N 크기의 벽을 2×1, 1×2, 1×1 크기의 타일로 채우는 경우의 수를 구해보자.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

첫째 줄에 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다.

---

풀이

아이디어

바텀 업으로 진행하였고, 다음과 같은 점화식을 지정하였다

또한 recursion제한을 정수범위 $1e6$까지 해제해주었다.

코드

import sys
sys.setrecursionlimit(int(1e6))
n = int(input())
dp = [0] * int(1e7)
dp[0], dp[1], dp[2] = 1, 2, 7

def tiling(n):
    if dp[n] != 0:
        return dp[n]
    
    else:
        dp[n] = (tiling(n-1)*3 + tiling(n-2) - tiling(n-3)) % 1000000007
    return dp[n]

print(tiling(n))

---

회고

규칙을 찾고 점화식을 내는게 까다로웠던 문제