728x90
[파이썬] 백준 11727 : 2xn 타일링 2
https://www.acmicpc.net/problem/11727
11727번: 2×n 타일링 2
2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다.
www.acmicpc.net
실버 3
DP
도저히 규칙을 못 찾아서 노가다로 경우의 수를 구해봤다.
1 : 1
2 : 3
3 : 5
4 : 11
5 : 21
...
3번째 의 5는 1번째의 1에 2를 곱한 값과 2번째의 3을 더한 값과 같다는 사실을 발견했다.
이를 점화식으로 나타내면
dp[i] = dp[i-2]*2 + dp[i-1]가 된다.
코드
import sys
n = int(sys.stdin.readline())
dp = [0] * 1001
dp[1] = 1
dp[2] = 3
for i in range(3, 1001):
dp[i] = dp[i-2]*2 + dp[i-1]
print(dp[n] % 10007)
728x90
'알고리즘 문제 풀이' 카테고리의 다른 글
| [파이썬] 백준 2210 : 숫자판 점프 (0) | 2022.03.28 |
|---|---|
| [파이썬] 백준 1260 : DFS와 BFS (0) | 2022.03.27 |
| [파이썬] 백준 1012 : 유기농 배추 (0) | 2022.03.26 |
| [파이썬] 백준 22659 : 구간 합 구하기4 (0) | 2022.03.24 |
| [파이썬] 백준 9461 : 파도반 수열 (0) | 2022.03.24 |