문제
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
'알고리즘 > 백준알고리즘' 카테고리의 다른 글
백준알고리즘 - 1759번 암호 만들기 - 파이썬(Python) (0) | 2020.06.17 |
---|---|
백준알고리즘 - 11048번 이동하기 - 파이썬(Python) (0) | 2020.06.15 |
백준알고리즘 - 2748번 피보나치 수 2 - 파이썬(Python) (0) | 2020.06.15 |
백준알고리즘 - 1003번 피보나치 함수 - 파이썬(Python) (0) | 2020.06.14 |
백준알고리즘 - 2747번 피보나치 수 - 파이썬(Python) (0) | 2020.06.14 |