문제링크
https://www.acmicpc.net/problem/11726
11726번: 2×n 타일링
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
www.acmicpc.net
코드
|
1
2
3
4
5
6
7
8
9
10
11
|
import sys
input = sys.stdin.readline
n = int(input())
d = [0]*1001
d[1] = 1
d[2] = 2
for i in range(3, n+1):
d[i] = d[i-1] + d[i-2]
print(d[n]%100007)
|
cs |
Point
- 다이나믹프로그래밍으로 접근
Overlapping Subproblem & Optimal Substructure
큰 문제를 작은 문제로 쪼갤 수 있으며 & 큰 문제는 작은 문제의 정답을 통해 계산한다.
- 풀이 방법:
d(n) = 2*n을 채우는 방법의 수
n번째에서 새롭게 할 수 있는 행동은 세로로 1개 배치 or 가로로 2개 배치
세로로 1개 배치하는 상황은 d(n-1)(=n-1개가 채워져있는 상황)에 추가로 새로 1개 배치하는 것과 동일하고
가로로 2개 배치하는 상황은 d(n-2)에 추가로 가로 2개 배치하는 것!!
--> d(n) = d(n-1) + d(n-2) 가 성립, d(1) = 1 , d(2) = 2
'Algorithm > Baekjoon' 카테고리의 다른 글
| [백준]9095 1, 2, 3 더하기 파이썬 python (0) | 2022.02.05 |
|---|---|
| [백준]11727 2*n타일링2 파이썬 python (0) | 2022.02.04 |
| [백준]1463 1로 만들기 파이썬 python (0) | 2022.01.15 |
| [백준]1261 알고스팟 파이썬 python (0) | 2022.01.15 |
| [백준]13549 숨바꼭질3 파이썬 python (0) | 2022.01.14 |