티바이트

문제 링크 (알고스팟)
https://algospot.com/judge/problem/read/ASYMTILING

문제 이해

2 x n크기의 직사각형 공간을 2x1혹은 1x2 크기의 타일로 완전히 채우는 방법의 수를 구하는 문제이다.

타일의 배치가 좌우대칭인 것은 제외한다.

풀이

예를 하나 뽑아서 2 x 6 크기의 공간을 채우는 경우를 생각해 본다.

여기서 2 x 6 크기의 공간을 채우는 여러 경우들을 2가지로 나눌 수 있다.

A. 맨 마지막 타일이 세로로 되어 있음

B. 맨 마지막 타일이 가로로 2개 되어 있음

남은 부분의 크기를 보면,

A의 경우 나머지 공간의 너비는 5이고

B의 나머지 공간의 너비는 4이다.

즉, A에서 남은 부분을 채우는 방법의 수는, 이 문제에서 너비가 5인 공간을 채우는 경우의 답과 같다.

B의 나머지 부분을 채우는 방법의 수 역시 너비가 4인 공간을 채우는 경우의 답과 같다.

여기서 이 문제의 재귀적 속성을 발견할 수 있으며

이 문제를 Dynamic Programing (동적 계획법)으로 풀 수 있다는 것을 알 수 있다.

상향식(bottom-up)으로 어떻게 풀 지를 구체적으로 생각해 보면,

- n=1 일 때 (1 가지)

- n=2 일 때 (2 가지)
- n=3 일 때는  (n=2의 가지수) + (n=1의 가지수)

'n=2의 가지수'는 위 그림에서 A의 경우이고, 'n=1의 가지수'는 위 그림에서 B이다.

- n=4일 때는 (n=3)의 가지수 + (n=2의 가지수)

...

...

..

n = k일 때는 (n=k-1 의 가지수) + (n=k-2 의 가지수)

어디서 본 적이 있는 점화식이 나온다. 바로 피보나치 수열이다.

그런데 문제에서 좌우대칭인 경우는 제외하라는 조건이 있다.

이번에는 채워야 할 공간의 크기가 짝수인 것과 홀수인 것으로 나누어 생각해야 한다.

공간의 크기가 홀수일 때 좌우대칭이 되기 위한 조건은

가운데에 블록이 세로로 있어야 하며 분할된 한 쪽 너비는 (int)n/2이다.

공간의 크기가 짝수일 때는 분할된 한 쪽 너비가 n/2이다.

분할된 너비에 해당하는 경우의 수를 빼면 최종적인 답을 구할 수 있다.

구현

대칭인 경우를 제외시키기 위해 너비의 절반을 구해야 하는데,

피보나치 수열을 구하는 과정에서 같이 계산하도록 했다.

그리고 답을 리턴할 때, 이 문제에서 나머지연산한 결과를 요구하므로

계산 과정에서 그 수를 초과하지 않도록 주의하여야 한다.

A - B%mod + mod 와 같이 더해주면 값이 음수가 되는 것을 방지할 수 있다.