Programmers / 2 x n 타일링 / Python

*문제 출처는 프로그래머스에 있습니다.

 

문제 제목: 2 x n 타일링 (2단계)

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/12900

프로그래머스

 

문제 설명

 

---

 

나의 풀이

 

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

    return dp[n-1]

 

n = 1일 때 result = 1, n = 2일 때 result = 2, n = 3일 때 result = 3, n = 4일 때 result = 5, n = 5일 때 result = 8

이렇게 dp[n] = dp[n - 1] + dp[n  - 2]가 된다.전과 전전의 합을 구해주면 쉽게 풀 수 있다. 문제를 보면 매 경우의 수를 1,000,000,007로 나눠야 하므로 이 점을 참고해서 풀면 된다.

---

※ 알아야 할 것

 

동적 계획법 문제는 점화식을 만들어서 풀면 쉽다.