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

문제 링크

성능 요약

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

분류

다이나믹 프로그래밍

제출 일자

2026년 04월 25일 22:04:59

문제 설명

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

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

입력

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

출력

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

---

💡 해결 방법

💻 코드

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