반응형
https://www.acmicpc.net/problem/11726
11726번: 2×n 타일링
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
www.acmicpc.net
소스코드
풀이
★ 2 x n 직사각형을 1 x 2, 2 x 1 타일로 채울 수 있는 방법의 수는 2 x (n-1)을 채울 수 있는 방법의 개수 + 2 x (n-2)를 채울 수 있는 방법의 개수입니다 !
★ 점화식을 세우기 위해선 패턴을 파악해야 합니다. n이 1부터 5일때까지를 대입해보면
n = 1, 방법: 1가지
n = 2, 방법: 2가지
n = 3, 방법: 3가지 (n이 1일 때 + n이 2일 때)
n = 4, 방법: 5가지 (n이 2일 때 + n이 3일 때)
n = 5, 방법: 8가지 (n이 3일 때 + n이 4일 때)
위와 같은 패턴을 점화식으로 만들어주면 됩니다 !
★ 결과값을 출력할 때 방법의 수를 10,007로 나눈 나머지를 출력해야 하는 것을 주의해야 합니다 :)
반응형
'Algorithm > 백준' 카테고리의 다른 글
| [백준 알고리즘] 14235번: 크리스마스 선물 (Python) (0) | 2023.08.18 |
|---|---|
| [백준 알고리즘] 1935번: 후위 표기식2 (Python) (0) | 2023.08.18 |
| [백준 알고리즘] 15815번: 천재 수학자 성필 (Python) (1) | 2023.08.18 |
| [백준 알고리즘] 2841번: 외계인의 기타 연주 (Python) (0) | 2023.08.18 |
| [백준 알고리즘] 11057번: 오르막 수 (Python) (3) | 2023.08.17 |