[코딩테스트 예제] 2 x n 타일링

문제 설명
가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.

타일을 가로로 배치 하는 경우
타일을 세로로 배치 하는 경우
예를들어서 n이 7인 직사각형은 다음과 같이 채울 수 있습니다.

직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.

제한사항
가로의 길이 n은 60,000이하의 자연수 입니다.
경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.
입출력 예
n result
4 5
입출력 예 설명
입출력 예 #1
다음과 같이 5가지 방법이 있다.

---

접근법
처음에는 조합을 이용하여 코드를 작성했다. 위의 예시에서 n = 4인 경우라고 했을 때

• 모두 세로인 경우 : 1가지
• 2개 세로 2개 가로인경우 : 3C1, 가로인 경우를 한묶음으로 생각해 3개(세로2, 가로1) 중 가로 1개가 위치할 경우를 구한다.
• 4개 가로인 경우 : 2C2, 가로인 경우가 2묶음으로 생각하고 구한다.

이런식으로 접근했을 때 정확도 테스트에서는 문제가 없지만 효율성 문제를 통과할 수 없었다.
따라서 다른 방법을 고민했고 n에따른 결과의 값들이 피보나치 수열을 이룬다는 것을 알 수 있었다.

내가 작성한 코드

## 최대 재귀깊이제한을 10**7로 설정, 파이썬은 기본적으로 1000으로 제한이 되어있다.
import sys
sys.setrecursionlimit(10**7)

## memoization을 위한 dictionary
memo = {1:1, 2:2}
def fact(n):
    if n in memo:
        return memo[n]
    else:
        result = (fact(n-1) + fact(n-2)) %  1000000007
        memo[n] = result
        return result

def solution(n):
    answer = 0
 
    answer = fact(n)  %  1000000007
 
 	return answer