코딩테스트/백준
[백준] 11727: 2×n 타일링 2 리뷰
윤호
2021. 2. 4. 11:46
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
그림을 보면 이해가 쉬울 듯 합니다.
점화식을 구하려다 보니 고등학생 때 수열 점화식을 구하는 것 처럼 규칙을 찾을 생각만 했었습니다. (계속 조합 생각밖에 안났었다..!) 이전 단계가 경우의 수를 포함하고 있다는 것을 계속 기억하고 있었다면 접근이 가능하지 않았을까 합니다.