[프로그래머스/파이썬] Level 3 2 X n 타일링

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

알고리즘 분류

• 다이나믹프로그래밍

문제풀이

백준에도 똑같은 문제가 있는 것으로 기억한다.

다이나믹프로그래밍 알고리즘을 적용해서 규칙을 찾아 적용해주면 된다.

이외에 변수 a,b만 사용해서 원하는 값을 구할수도 있다.

소스코드

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

더 간단한 코드

def solution(n):
    a, b = 1, 1
    for i in range(1, n):
        a, b = b, (a + b) % 1000000007
    return b