카테고리 없음
[python][백준/BOJ] 11727번 : 2×n 타일링 2
haju
2023. 7. 6. 16:48
https://www.acmicpc.net/problem/11727
11727번: 2×n 타일링 2
2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다.
www.acmicpc.net
✅ 문제 풀이
- n=1 ➡ 1
- n=2 ➡ 3
- n=3 ➡ 5
- n=4 ➡ 11
- n=5 ➡ 21
- ...
dp[i]= dp[i-1] + 2 * dp[i-2]
✅ 최종 코드
import sys
n=int(sys.stdin.readline())
dp=[0]*1001
dp[1]=1
dp[2]=3
for i in range(3,n+1):
dp[i]=dp[i-1]+2*dp[i-2]
print(dp[n]%10007)