728x90
11726번: 2×n 타일링
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
www.acmicpc.net
분석
D[N] : 길이 N으로 만들 수 있는 타일의 경우의 수
- D[N-1] : n-1까지 타일이 채워져있는 경우 ➔ 새로운 타일 1개를 채워 N길이를 만듦
- D[N-2] : n-2까지 타일이 채워져있는 경우 ➔가로로 타일 2개를 래워 N길이를 만듦
D[N] = D[N-1]+D[N-2]
풀이
# 2*n크기 직사각형을 2*1/1*n으로 채우는 방법의 수
n = int(input())
d=[0]*1001 # n의 최댓값 1000
d[1]=1
d[2]=2
for i in range(3, n+1):
d[i]= d[i-1]+d[i-2]
print(d)
print(d[n]% 10007)
728x90