0212. [BOJ#11727] 2×n 타일링 2

1 초

256 MB

72547

43104

34700

58.847%

문제

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

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

입력

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

 

출력

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

---

함수를 쓰면 시간초과가 난다.

제출 코드

import sys
input = sys.stdin.readline

n = int(input())
lst = [0] * 1001
lst[1] = 1
lst[2] = 3

for i in range(3, 1001):
    lst[i] = lst[i-1] + (lst[i-2] * 2)

print(lst[n]%10007)

for 문을 쓴 경우

제출 코드2

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n = int(input())

def recur(n):
    if n == 1:
        return 1
    elif n == 2:
        return 3
    
    return recur(n-1) + (recur(n-2) * 2)

result = recur(n)
print(result%10007)

함수를 쓴 경우 (시간초과가 난다)

 

4번까지 직접 해보고 점화식을 구해서 풀었다.. n=4 일 때의 경우의 수를 잘못구해서 너무오래걸렸다..