11727번: 2×n 타일링 2
2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다.
www.acmicpc.net
풀이는 해당 블로그를 참고했습니다.
1. 2x(N-1)만큼 타일링하고 2x1 타일을 붙인다.
2-1. 2x(N-2)만큼 타일링하고 1x2 타일을 두 개 붙인다.
2-2. 2x(N-2)만큼 타일링하고 2x2 타일을 한 개 붙인다.
따라서 d(i) = d(i-1) + d(i-2) * 2
그림을 보면 이해가 쉬울 듯 합니다.
점화식을 구하려다 보니 고등학생 때 수열 점화식을 구하는 것 처럼 규칙을 찾을 생각만 했었습니다. (계속 조합 생각밖에 안났었다..!) 이전 단계가 경우의 수를 포함하고 있다는 것을 계속 기억하고 있었다면 접근이 가능하지 않았을까 합니다.
'코딩테스트 > 백준' 카테고리의 다른 글
| [백준] 2133: 타일 채우기 파이썬 리뷰 (0) | 2021.02.13 |
|---|---|
| [백준] 10844: 쉬운 계단 수 파이썬 리뷰 (0) | 2021.02.04 |
| [백준] 1202(보석 도둑) 파이썬 (0) | 2021.01.27 |
| [백준] 2437(저울) 파이썬 (0) | 2021.01.27 |
| [백준] 1697(숨바꼭질) 파이썬 (0) | 2021.01.05 |
댓글