바닥 공사

1. 문제 설명

가로 길이가 N, 세로 길이가 2인 직사각형 형태의 바닥이 있다. 우리는 이 바닥을 (1 * 2), (2 * 1), (2 * 2) 3 가지 타일로 바닥을 채우려 한다. 

 

이 때 바닥을 채울 수 있는 모든 경우를 구하는 프로그램을 구하시오. 예를 들면 2 * 3 바닥을 채우는 경우는 5가지가 나온다.

 

입력 조건은 다음과 같다.

 

- N ( 1 ≤ N ≤ 1000 )

- 바닥을 채우는 경우의 수를 796,796으로 나눈 나머지를 출력한다.

2. 문제 해결

앞서 문제를 푼 개미전사 문제와 비슷하다. 특정한 조건 또는 연산으로 점화식을 구성할 수 있는지 묻는 문제이다. 이 경우 DP의 전형적인 유형이라고 할 수 있다.

 

이 또한 그림을 그리면서 해결하면 어렵지 않다. 아마 예를 들면서 2 ~ 3번 그림을 그리면 다음과 같은 규칙을 찾을 수 있을 것이다.

 

 

1. 왼쪽부터 i - 1 까지의 길이가 채워져 있다고 가정, 그러면 2 * 1 블럭의 타일만 채우면 i 길이의 바닥을 얻는다.

2. 왼쪽부터 i - 2 까지의 길이가 채워져 있다고 가정, 그러면 2개의 1 * 2 블럭 or 1개의 2 * 2 블럭으로 채우면 i 길이의 바닥을 얻는다.

 

개미 문제와 마찬가지로, N - 2 미만에 타일에 대해선 고려할 필요가 없다. 사용할 블럭( 연산 )의 크기가 최대 2 * 2 라서, 바닥을 채울 수 있는 모든 경우는 위 2 가지 경우밖에 없다. 이를 점화식으로 표현하면 다음과 같다. ( a[i]는 해당 위치에서 블럭을 채우는 경우의 수 )

 

a[i] = a[i-1] + a[i-2] * 2

 

이를 코드로 표현하면 다음과 같다.

 

3. 느낀 점

역시 코드는 단순하다. 하지만 이를 거치기 위해 진행한 과정이 꽤 복잡한 걸 확인 할 수 있다.

 

앞서 말했듯, DP 유형임을 확인하면 점화식을 세우고 바로 코드로 구현하면 된다. bottom-up이 점화식에 맞추기 가장 적합한 방법이기도 하다.