[프로그래머스] 2 x n 타일링 - Python

📍문제

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

 

📍풀이: DP로 경우의 수 메모이제이션

타일을 배치하는 경우의 수를

i. 세로 타일로 시작할 때 (| 모양 스타트)

ii. 아닐 때 (= 모양 스타트)

 

크게 이렇게 구분할 수 있음

 

n = 1 이라면

i. 1

ii. 0

-> 1

 

n = 2 

i. 1

ii. 1

-> 2

 

n = 3

i. n = 2의 경우의 수 (2) (| 모양 채웠으므로 나머지 2개 영역만 채우면 됨)

ii. n = 1의 경우의 수 (1) (= 모양 채웠으므로 나머지 1개 영역만 채우면 됨)

 

n = 4

i. n = 3의 경우의 수

ii. n = 2의 경우의 수

 

n = 5

i. n = 4의 경우의 수

ii. n = 3의 경우의 수

 

그렇다면 f(n) = f(n - 1) + f(n - 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]