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