Programmers - 2 x n 타일링

문제 링크

d[i] : 2 x n 타일을 배치할 수 있는 경우의 수 라고 할때

d[i] = d[i-1] + d[i-2] 이다

i-1칸으로 만드는 방법들에서 세로로 1칸 붙이는 방법이 있고
i-2칸으로 만드는 방법들에서 가로로 2칸을 붙이는 방법이 있기 때문.

def solution(n):
    mod = 1000000007

    d = [0 for _ in range(n+1)]
    d[0] = 1
    d[1] = 1
    for i in range(2, n+1):
        d[i] += d[i-1]
        d[i] += d[i-2]
        d[i] %= mod

    return d[n]