[프로그래머스] Level3, 2 x n 타일링 (Python)

문제

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

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

 

코드

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

세로의 길이 1, 가로의길이가 2인 타일로 세로의 길이가 2, 가로의 길이가 n인 바닥을 가득 채우는 경우에 수를 구하는 문제이다.

 

경우에 수를 따져보면 n이 1일때 1가지 경우의 수, 2일때 2, 3일때 3, 4일때 5, 5일때 8, 6일때 13 ... 피보나치 수열을 따르면서 증가하기 때문에 피보나치 수열로 메모제이션 하면서 풀면된다.