[백준] 11725번: 2×n 타일링

백준 11725번: 2×n 타일링

https://www.acmicpc.net/problem/11726

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	63385	23365	17179	34.648%

문제

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

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

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

출력

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

예제 입력 1

2

#예제 출력 1

2

예제 입력 2

9

예제 출력 2

55

출처

문제를 만든 사람: baekjoon

풀이

직사각형의 세로는 2로 고정되어 있다. 2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 구하는 함수를 f(n)으로 설정한다. f(1) = 1, f(2) = 2이며, f(n)은 f(n-1)에 1x2 타일을 붙이는 경우 + f(n-2)에 2x1 타일을 2개 붙이는 경우이다. 이를 수식으로 나타내면 다음과 같다.

𝑓(𝑛) = 𝑓(𝑛−1) + 𝑓(𝑛−2)

이는 피보나치와 같다..

n = int(input())
methods = list(range(n+1))
# methods[1] = 1
# methods[2] = 2
# 이미 설정되어 있음.

for i in range(3, n+1):
  methods[i] = (methods[i-1] + methods[i-2]) % 10007

print(methods[n])

채점이 무진장 오래 걸린다 (한 2분??)