반응형
11727
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
|
import sys
N = int(sys.stdin.readline())
dp = [-1]*1001
dp[1] = 1
dp[2] = 3
for i in range(3,N+1):
dp[i] = dp[i-2]*2 + dp[i-1]
print(dp[N]%10007)
|
cs |
.
.
.
[풀이]
dp로 풀면 되는 간단한 문제.
점화식을 세우기 위해 i = 1, 2, 3, 4까지 일일이 해봤다.
dp[i] = dp[i-2]*2 + dp[i-1] 라는 규칙만 파악하면 된다.
타일이 있니 뭐니 하는 것은 그저 복잡하게 보이려는 눈속임일 뿐.
p.s.
약 4개월만에 백준을 풀었다.
파이썬보다 C++에 관심이 생겨 공부중이다.
파이썬을 까먹지 않도록 매일 한 문제씩 풀 예정이다.
반응형
'백준 문제풀이' 카테고리의 다른 글
| [백준 2512] 파이썬 : 예산 (0) | 2022.03.07 |
|---|---|
| [백준 1417] 파이썬 : 국회의원 선거 (0) | 2022.03.02 |
| [백준 11728] 파이썬 : 배열 합치기 (0) | 2021.10.27 |
| [백준 1789] 파이썬 : 수들의 합 (0) | 2021.10.26 |
| [백준 5635] 파이썬 : 생일 (0) | 2021.10.23 |