프로그래머스 / DP / 2 * n 타일링

문제

---

 

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

프로그래머스

 

입출력

---

 

 

해설

---

 

타일링 문제이고 전형적인 DP문제이다.

 

문제에서 주어지는 타일은 2 * 1, 1 * 2 타일 2가지이다.

그럼 만들 수 있는 모양의 가짓수는 이전의 모양에서 1 * 2를 사용하여 만드는 것과 2 * 1 모양 2개를 이용하여 만드는 방법이 있다.

 

DP[i] := 2 * i 타일을 채우는 가짓 수

라고 할 때 

 

위 그림 같은 2가지 방법이 있다.

DP[i] := DP[i - 1] + DP[i - 2] 가 된다. 

 

 

정답코드

---

'''
'25. 10. 19.(일)

1. 2 * n 타일링을 채우는 방법을 알아내어라

n : 1 1
n : 2 2
n : 3 3
n : 4 5

DP[i] := DP[i - 1] + DP[i - 2]

'''
def solution(n):
    MOD = 10**9 + 7
    dp = [0] * (n + 1)
    dp[0] = dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = (dp[i-1] + dp[i-2])%MOD
    return dp[n]

 

깃허브 : https://buly.kr/1xzVA6p

유튜브 : https://youtu.be/XFWiiLVIf_E