출처
Koreatech OnlineJudge(링크)
문제이해
3xN길이의 판을 1x1 블럭과 2x2 블럭으로 채울 때 판을 꽉 채울 수 있는 방법의 수를 구하는 문제이다. 피보나치 수열을 사용하여 푸는 1056번 문제를 풀었다면 응용하여 풀 수 있다.
문제접근
n번째 항을 구할 때 n-1번째 항과 n-2번째 항의 값을 가지고 구할 수 있다.
먼저 n-2항에서 n항으로 확장하는 방법은 [그림 1] 처럼 2가지이다.
[그림 1]
그리고 n-2항에서 n항으로 확장하는 방법은 [그림 2] 처럼 1가지이다.
[그림 2]
따라서 점화식은
이다.
[그림 3]에서와 같이 n-2항에서 1x1타일 6개를 확장할 수도 있기 때문에
혼동하기 쉬운데, 이 경우는 [그림 2]의 경우에 포함되므로 계산하지 않아야 한다.
[그림 3]
구현
첫 번째 항을 1로 하고, 두 번째 항을 3으로 하여 위 점화식을 반복하여 계산하면 된다.
숫자가 커질 수도 있으므로 오버플로에 주의하며 1,000,000,007로 나누어야 한다.
또한, N=1인 입력도 있으므로 이 경우에도 올바른 값이 나오도록 해야 한다.
실행결과
코드
https://github.com/tibyte/algorithm-problems/blob/master/koreatech/1055/1055.cpp