<문제 링크>
https://algospot.com/judge/problem/read/GRID
문제
We wish to tile a grid 4 units high and N units long with rectangles (dominoes) 2 units by one unit (in either orientation). For example, the figure shows the five different ways that a grid 4 units high and 2 units wide may be tiled.
Write a program that takes as input the width, W, of the grid and outputs the number of different ways to tile a 4-by-W grid.
입력
The first line of input contains a single integer N, (1 ≤ N ≤ 1000) which is the number of datasets that follow.
Each dataset contains a single decimal integer, the width, W, of the grid for this problem instance.
출력
For each problem instance, there is one line of output: The problem instance number as a decimal integer (start counting at one), a single space and the number of tilings of a 4-by-W grid. The values of W will be chosen so the count will fit in a 32-bit integer.
경우의 수를 구하는 문제 이므로 동적계획법을 통해 정답을 구할 수 있다. 문제는 4 * W 의 판에 2 * 1의 grid를 빈틈없이 배치하는 경우의 수를 구하는 것이고 이때 배치할 수 있는 모든 경우의 수가 해답이된다. 본 문제의 최적 구분 구조를 만족한다. 증명은 너무나 직관적이므로 생략한다. 본 문제의 적절한 부분문제를 정의하고 점화식을 세우면 문제를 해결한거나 마찬가지다. 본문제의 모든 경우의 수를 고려하는 추상화는 튀어나온 블럭의 경우의수를 고려하는 것이다. 문제를 해결하기 위한 논리의 흐름을 설명하면 아래와 같을 것이다.
T[W] = 4 * W크기의 판을 꽉 차게 채우는 경우의 수
이때 우리는 T[a](0 < a < W)의 값을 통해서 T[W]의 값을 구해야 된다. 그런데 지금처럼 부분 문제를 정의해버리면 점화식을 세우기가 굉장히 까다롭다. 왜냐하면 T[a]의 경우에 포함되지 않는 경우에서도 T[W]에 해당하는 경우가 존재 하기 때문이다. 예를 들면 아래와 같다.
W = 5 라고 가정하면 W = 4 또는 3 경우에서 T[4], T[3]의 값을 이용해 T[5]에 포함되는 일부의 경우의 수를 구할 수 있지만 이에 포함되지 않는 경우 예를들어서 4번째 열의 세로 네 칸중에서 아래 두칸만 채워진 경우(3번째 열에 걸쳐져서) 또는 네칸중 가장 윗칸과 가장 아랫칸만 채워진 경우 등은 이에 해당하지 않기때문이다. 하지만 이러한 경우에서도 T[5]에 포함되는 경우를 포함한다. 즉 이 문제를 풀기 위해서는 세로로 채워진 블럭만을 고려하지않고 가로로 2 * 1의 블럭이 채워 졌을때 지금 고려하는 열과 이전열에 블럭이 걸쳐진 경우까지 고려하여 부분문제를 정의 하여야 된다.
k = 열의 상태
k = 0 : 열이 텅빈 상태
k = 1 : 네칸 중 아래 두칸만 채워진 상태(세로로 채워진 경우는 포함되지 않는다. 이전 칸과 걸쳐진 경우만 포함시킨다.)
k = 2 : 네칸중 위쪽 두칸만 채워진 상태(k = 1과 제약조건 동일)
k = 3 : 가운데 두칸만 채워진 상태
k = 4 : 가장위쪽한칸 그리고 가장 아래쪽 한칸만 채워진 상태(위쪽과 제약 조건 동일)
k = 5 : 열이 모두 채워진 상태(제약조건 없음, 이전 열에 걸쳐세 채워지는 경우 그리고 열에 세로로 두개의 조각이 채워지는 경우 모두 포함)
결국 우리가 구하는 정답은 T[W][5]가 된다.
점화식을 세워보면 아래와 같다
T[w][0] = T[w - 1][5]
T[w][1] = T[w - 1][0] + T[w - 1][2]
T[w][2] = T[w - 1][0] + T[w - 1][1]
T[w][3] = T[w - 1][4]
T[w][4] = T[w - 1][0] + T[w - 1][3]
T[w][5] = T[w][0] + T[w][1] + T[w][2] + T[w][4] + T[w - 1][0] (마진막에 더해진 항은 네칸 모두가 w - 1열과 w열에 걸쳐져서 가로로 채워진 경우이다. 현재 부분 문제를 정의 하는데 있어서 네칸 모두 걸쳐져서 채워진 경우는 제외 시켰기 때문에 답을 구하는 과정에서 이같이 포함시켜야 된다. 애초에 부분문젤르 더 간결하고 명확하게 정의하는것이 더 좋은 방법이기는 한것 같다.)
초항은 아래와 같다.
T[1][0] = 1 T[1][1] = T[1][2] = T[1][3] = T[1][4] = 0
T[1][5] = 1
이제 위와같은 점화식을 bottom-up방식의 동적계획법으로 구현하면 아래와 같다.
#include<iostream>
#include<vector>
using namespace std;
unsigned int w;
int main() {
int cases;
cin >> cases;
int cnt = 1;
while (cases--) {
cin >> w;
//예외 처리
if (w == 0) {
cout << cnt << " " << 0 << endl;
++cnt;
continue;
}
vector<vector<int> > t(w + 1, vector<int>(6, 0));
t[1][0] = 1; t[1][1] = 0;
t[1][2] = 0; t[1][3] = 0;
t[1][4] = 0; t[1][5] = 1;
for (unsigned int i = 2; i <= w; ++i) {
t[i][0] = t[i - 1][5];
t[i][1] = t[i - 1][0] + t[i - 1][2];
t[i][2] = t[i - 1][0] + t[i - 1][1];
t[i][3] = t[i - 1][4];
t[i][4] = t[i - 1][0] + t[i - 1][3];
t[i][5] = t[i][0] + t[i][1] + t[i][2] + t[i][4] + t[i - 1][0];
}
cout << cnt << " " << t[w][5] << endl;
++cnt;
}
}