[Python][프로그래머스][Level3] 2xn 타일링

[Python][프로그래머스][Level3] 2xn 타일링

코드

def solution(n):
    if n<=2:
        return 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]

Dynamic Programming으로 풀었다.

1,2개 일 때를 제외하고 생각을 해보면

마지막 2개의 타일이 “=” 인 개수 = n-2개 타일로 만든 개수

따라서 dp[n]=dp[n-1]+dp[n-2] 이다.

사실 몇개를 직접 해보면 점화식이 세워진다.