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

문제 설명

알고리즘 고민

n이 5일 때까지를 손으로 계산해서 얼마나 나왔는지 정리해보았다. 정리해본 결과, n이 1일 때 1, n이 2일 때 2, n이 3일 때 3, n이 4일 때 5, n이 5일 때 8이었다. 이를 통해 피보나치의 규칙이 있다는 것을 알았고 이를 메모이제이션(Memoization) 방법을 사용하여 해결하였다. 제한사항에 경우의 수가 많아질 수 있으므로, 경우의 수를 1,000,000,007로 나눈 나머지를 return하라는 조건에 그냥 n번째 값을 1,000,000,007로 나눴는데 값이 너무 커서 오류가 발생한 걸로 생각된다. 따라서 메모이제이션을 적용할 때 나눈 나머지를 넣어 값을 제한하여 해결하였다.

코드

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