프로그래머스 level3 [ 2 x n 타일링] 파이썬

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

코딩테스트 연습 - 2 x n 타일링

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

# 프로그래머스 2 x n 타일링

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

위의 문제는 피보나치 수열을 이용한 dp 문제이다.

i번째의 경우의 수 = i-2번째에  '=' 처럼 가로 블럭을 두 개 쌓는 경우 와 i-1 번째에 ' | ' 처럼 세로 블럭 하나를 쌓는 경우를 합한 것이다.