티바이트


출처 

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





 


댓글을 다는 공간입니다. (로그인하지 않아도 댓글을 남길 수 있습니다.)



게시판 목록은 좌측상단에 있습니다.

Statistics Graph