문제링크
https://www.acmicpc.net/problem/11727
11727번: 2×n 타일링 2
2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다.
www.acmicpc.net
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
import sys
input = sys.stdin.readline
n = int(input())
d = [0]*1001
d[1]=1
d[2]=3
for i in range(3, n+1):
d[i] = (d[i-1] + 2*d[i-2])%10007
print(d[n])
|
cs |
Point
- 다이나믹프로그래밍으로 접근
Subproblem 만족 & Optimal Substructure
- 풀이 방법:
d(n) = 2*n을 채우는 방법의 수
n번째에서 새롭게 할 수 있는 행동은
(1) d(n-1)에 추가로 1*2타일 1개 배치하기
(2) d(n-2)에 추가로 2*1타일 2개 배치하거나 OR 2*2타일 1개 배치하기
--> d(n) = d(n-1) + 2*d(n-2) 가 성립, d(1) = 1 , d(2) = 3
'Algorithm > Baekjoon' 카테고리의 다른 글
| [백준]11052 카드구매하기 16194 카드구매하기2 파이썬 python (0) | 2022.02.06 |
|---|---|
| [백준]9095 1, 2, 3 더하기 파이썬 python (0) | 2022.02.05 |
| [백준]11726 2*n 타일링 파이썬 python (0) | 2022.01.16 |
| [백준]1463 1로 만들기 파이썬 python (0) | 2022.01.15 |
| [백준]1261 알고스팟 파이썬 python (0) | 2022.01.15 |