프로그래머스) 2 x n 타일링-python

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

프로그래머스

 

 

사실 문제를 어떻게 풀어야할지 감도 잡히지 않았다.

그리디, DFS, BFS 스택,큐, 정렬...

그리고 경우의수를 생각했을 때 절대 내가 알고있는 알고리즘으로 풀 수 없다고 생각했고

검색을 해보았다.

 

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

 

문제는 DP문제였다.

n이 4개일때 5.

그럼 n이 3일때는 3이다.

n이 2일때는 2, 1인 경우는 1

1부터 4까지 순서대로, 1 2 3 4이고 이 경우엔 n = n-1 + n-2의 법칙이 성립하게 된다.