[프로그래머스] 2 x n 타일링 풀이

1. 문제

https://programmers.co.kr/learn/courses/30/lessons/12900?language=python3

2. 풀이 방법

arr[i] 의 값을 구하기 위해서는 아래의 2가지 경우의 수가 존재합니다.

• arr[i-1] 의 모든 경우의 수에서 세로 막대기 1개를 추가하는 경우
• arr[i-2] 의 모든 경우의 수에서 가로 막대기 2개를 추가하는 경우(세로 막대 2개를 추가하는 경우는 이미 위의 케이스에 해당 됨)

즉, arr[i] = arr[i-1] + arr[i-2] 인 것을 알 수 있습니다.

3. 소스코드

3.1. python 시간 초과 코드

숫자가 매우 커져 연산 속도가 느려지기 때문에, 시간 초과 발생

def solution(n): 
    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] ) 
    return arr[n] % 1000000007

3.2. python 정답 코드

def solution(n): 
    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] % 1000000007