Hikenny25
11727 - 2×n 타일링 2 본문
https://www.acmicpc.net/problem/11727
11727번: 2×n 타일링 2
2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다.
www.acmicpc.net
- Dynamic Programming
import sys
input = sys.stdin.readline
n = int(input())
dp = [0] * (n+2)
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)
타일링 문제 1에서 언급했던 경우의 수에,
n-2 길이의 상자에 (가로 2, 세로 2) 정사각형을 추가하여 길이가 n인 상자를 만드는 경우의 수를 추가하여
dp[n] = dp[n-1] + 2 * dp[n-2]
가 된다.
'baekjoon (solved.ac) > class 3 Solve' 카테고리의 다른 글
| 9461 - 파도반 수열 (0) | 2022.10.25 |
|---|---|
| 11659 - 구간 합 구하기 4 (0) | 2022.10.25 |
| 11726 - 2×n 타일링 (0) | 2022.10.25 |
| 1260 - DFS와 BFS (0) | 2022.10.25 |
| 2606 - 바이러스 (0) | 2022.10.25 |
Comments