1. 문제 설명

2XN 타일링

2. 문제 분석

DP를 통해 이전에 계산한 값을 그대로 활용한다. 사실 문제가 DP인지는 직접 직사각형을 몇 개 그려본 뒤 알 수 있었는데, 초기값을 그대로 활용했을 때 피보나치임을 알 수 있었다. DP로 문제를 풀기 위해서는 점화식을 찾은 뒤 크기에 알맞은 리스트를 만든 뒤 식을 반복하면 된다.

3. 나의 풀이

def solution(n):

    dp = [0]*n
    dp[0] = 1
    dp[1] = 2
    for i in range(2, n):
        dp[i] = (dp[i-2] + dp[i-1])%1000000007
    return dp[n-1]