https://www.acmicpc.net/problem/11727
11727번: 2×n 타일링 2
2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다.
www.acmicpc.net
풀이 과정
2xn 모양의 타일이 있으면 2x1 타일을 하나 더 붙여서 2x(n+1) 타일을 만들 수 있고
1x2 타일을 2개 붙이거나, 2x2 타일을 붙여서 2x(n+2) 타일을 만들 수 있다
따라서 d[n] = d[n-1] + 2d[n-2] 라는 점화식이 성립하고, 이를 통해 문제를 해결할 수 있다
소스 코드
d = [0, 1, 3]
n = int(input())
for i in range(3, n+1):
d.append(2*d[i-2] + d[i-1])
print(d[n] % 10007)'알고리즘 문제 풀이 > 백준' 카테고리의 다른 글
| 백준 11052 - 카드 구매하기 [파이썬] (0) | 2022.04.11 |
|---|---|
| 백준 9095 - 1, 2, 3 더하기 [파이썬] (0) | 2022.04.09 |
| 백준 11726 - 2xn 타일링 [파이썬] (0) | 2022.04.07 |
| 백준 1463 - 1로 만들기 [파이썬] (0) | 2022.04.07 |
| 백준 17103 - 골드바흐 파티션 [파이썬] (0) | 2022.04.07 |