[파이썬] 2 x n 타일링 [CODING TEST #57]

https://school.programmers.co.kr/learn/courses/30/lessons/12900

 

 

동적계획법(DP)으로 해결..

가로 블럭을 사용하면 무조건 2 x 2를 채워야 한다. 그래서 가로 기준 i-1번째까지 채웠을 때는 세로 블럭을 추가하는 방법 뿐이고, i-2번째까지 채웠을 때는 가로 블럭 2개를 추가하는 방법 뿐이다. i-2번째에서 세로 블럭을 채우는 건 dp[i-1]과 겹치므로 제외한다.

따라서 dp[i] = dp[i-1] + dp[i-2]가 성립한다.

 

 

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