[Lv.2 / 프로그래머스 / 파이썬] 2 x n 타일링

 

 

 

 

 

프로그래머스

 

 

 

풀이

 

2 x n 의 공간이 주어질 때 2 x 1 의 타일을 놓는 경우의 수를 구해야 하는 동적 계획법 문제이다.

n이 1 증가할 때 타일을 놓는 방법은 다음과 같다.

 

1. dp[n]일 때의 경우에 세로로 타일을 놓는다
2. dp[n-1]의 경우에 가로로 2칸짜리 타일을 놓는다

 

따라서 점화식은 dp[n] = dp[-1] + dp[-2] 이다.

 

def solution(n):
    dp = [0, 1, 2]
    for i in range(n - len(dp) + 1):
        dp.append((dp[-1] + dp[-2]) % 1000000007)
    return dp[n]