728x90
https://www.acmicpc.net/problem/11726
11726번: 2×n 타일링
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
www.acmicpc.net
DP 문제가 DP로 풀어야 한다는 것을 알고 시작하면, 별로 어려운 거 같지는 않다.
하지만 보통 시간에 막히고 그 때서야 깨닫게되어서 문제이지만...
간단하게 보면 타일은 세로로 1칸 차지하거나, 가로로 2개를 사용해서 2칸 차지하는 2가지 방법 밖에 없다.
결국 n-2일 때의 타일에 가로로 2칸 차지해서 만드는 경우와 n-1일 때 세로로 1칸 차지해서 만드는 경우를 더해주면 된다.
import sys
n = int(sys.stdin.readline())
square = [1 for i in range(n + 1)]
for i in range(2, n + 1):
square[i] = square[i-1] + square[i-2]
print(square[-1] % 10007)'알고리즘 > 동적 프로그래밍' 카테고리의 다른 글
| 백준 9251 LCS (Python) (0) | 2024.01.20 |
|---|---|
| 백준 11053 가장 긴 증가하는 부분 수열 (0) | 2024.01.20 |
| 백준 12865 평범한 배낭 (0) | 2024.01.20 |
| 백준 2193 이친수 (0) | 2024.01.17 |
| 백준 2839 설탕 배달 (0) | 2024.01.16 |