[Silver III] 2×n 타일링 - 11726

문제 링크

성능 요약

메모리: 32412 KB, 시간: 40 ms

분류

다이나믹 프로그래밍

제출 일자

2026년 04월 25일 22:04:59

문제 설명

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

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

입력

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

출력

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

---

💡 해결 방법

💻 코드

 
# 문제
# 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
 
# 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
 
 
 
# 입력
# 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
 
# 출력
# 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
 
n = int(input())
 
 
 
p = [1, 1, 2, 3, 5]
 
 
 
for i in range(len(p) - 1, 1000 + 1):
    p.append(0)    
    p[i] = (p[i - 1] + p[i - 2]) % 10007
 
 
 
print(p[n])