IT-garden

문제

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍 

정답

import sys

n=int(input())
m=[0]*(n+1)

def _11727(n):
    if n == 1:
        return 1
    if n == 2:
        return 3
    if m[n] != 0:
        return m[n]  
     
    m[n] = (_11727(n-1) + 2 * _11727(n-2) ) % 10007
    return m[n]

sys.setrecursionlimit(10000)
print(_11727(n))

sys.setrecursionlimit(10000)
sys 모듈을 이용해 재귀 한도를 10000까지 바꿔줍니다.
파이썬에서는 재귀호출을 무한이 아닌 1000번으로 제한중입니다.

백준 알고리즘 11727번 : www.acmicpc.net/problem/11727