발상 1
모든 블럭들은 서있거나 누워있거나 2가지 중 하나의 상태만을 가진다. 이 때, 누워있는 블럭들은 다음 행 배치에 영향을 주지 못한다. 따라서 서있는 블럭들의 위치만 추려서 각 행의 블럭 상태를 비트마스크로 표현하고 각 행의 각 상태에서 발생하는 모든 경우의 수의 합을 계산하면 된다. 마지막 행에서는 서있는 블럭을 사용할 수 없으므로 블럭을 놓을 수 있는 공간이 짝수인지 여부만 검사해 짝수라면 1개의 경우의 수를, 홀수라면 0개의 경우의 수를 반환한다. 발상은 간단하지만 코드가 매우 복잡하다. 또, 누워있는 블럭은 2칸으로 취급되기 때문에 비트마스크 계산 복잡도가 올라간다. 같은 상태의 비트마스크가 여러 번 발생할 수 있기 때문에 중복 여부를 검사한다고 해도 효율적인 알고리즘이라고 보기 힘들다.
점화식 1
점화식은 간단하다. 각 행마다 모든 배치를 시도하며 마지막 줄에서만 배치에 대한 정합성을 검사하며 된다.
코드 1
#include <iostream>
#include <vector>
#include <cstdlib>
#include <string>
#include <algorithm>
#include <stack>
using namespace std;
using ll = long long;
const int mod = 9901;
int n, m;
// 눕 0, 세 1
// 막줄이면 투페어 검사해서 통과하면 1 탈락이면 0
// 컨닝과 다른 점은 무조건 모든 칸을 채워야 함
vector<vector<int>> dp;
int r(int row, int st) {
int& ret = dp[row][st];
if (ret != -1) return ret;
if (row == n) { // 막줄이면 남은 모든 칸에 눕으로 배치가 가능한지 검사
int sign = 0;
for (int i = 0; i < m; i++) {
// 현재 칸이 눕인데 다음 칸이 비어있지 않거나 마지막 칸이면 오류
if(((st & (1 << i)) == 0 && (((st & (1 << (i + 1))) > 0) || i == m - 1))) {
sign = 1; break;
}
// 연속하는 두칸이 비어있으면 1칸 넘어감
else if (((st & (1 << i)) == 0 && (st & (1 << (i + 1))) == 0)) {
i++; continue;
}
}
return ret = 1 - sign; // 모든 칸에 눕을 배치할 수 있으면 1, 불가능하면 0
}
ret = 0;
vector<int> fp;
for (int i = 0; i < m; i++) {
if ((st & (1 << i)) == 0) { // 블럭을 배치할 수 있는 칸 위치 추출
fp.push_back(i);
}
}
vector<int> stch(1 << m);
for (int i = 0; i < (1 << fp.size()); i++) {
if (fp.size() > 0 && fp[fp.size() - 1] == m - 1 && (i & (1 << (fp.size() - 1))) == 0) continue; // 마지막 칸에는 눕힐 수 없음
int nst = 0; int cs = i; vector<int> ch(m); int sign = 0;
for (int j = 0; j < fp.size(); j++) {
if (ch[fp[j]] == 1) continue; // 이미 배치된 위치면 continue; ( 눕일 경우 다음 공간까지 잡아먹음 )
if ((cs & (1 << j)) == 0) {
if ((st & (1 << fp[j])) == 0 && (st & (1 << (fp[j] + 1))) == 0) { // 눕혀놓을 공간 있으면 눕히기
ch[fp[j]] = 1; ch[fp[j] + 1] = 1;
}
else {
sign = 1; break; // 공간 없으면 잘못된 배치임
}
}
if ((cs & (1 << j)) > 0) {
if ((st & (1 << fp[j])) == 0) { // 세우는 경우 비트마스크에 표시
ch[fp[j]] = 1;
nst |= (1 << fp[j]);
}
}
}
if (stch[nst] == 1 || sign == 1) continue; // 이미 사용한 비트마스크인 경우 탐색하지 않음
stch[nst] = 1;
ret += r(row + 1, nst); // 합계 계산
ret %= mod;
}
return ret;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
if (n % 2 == 1 && m % 2 == 1) { // 격자판 칸 수가 홀수인 경우 절대 채울 수 없음
cout << 0; return 0;
}
dp = vector<vector<int>>(n + 1, vector<int>(1 << m, -1));
cout << r(1, 0);
return 0;
} 발상 2
발상 1은 어째 너무 노가다스럽다. 시간도 오래 걸리고 코드도 복잡하다.
AC를 받긴 하지만 실행 시간이 500ms 를 넘어간다.
좀 더 정연한 풀이는 없는걸까 ?
다시 한번 생각해보자. 현재 칸에 영향을 줄 수 있는 위치는 어디일까?
어느 위치에 블럭을 다르게 배치했을 때 현재 칸 배치에 영향이 올 수 있을까 ?
탐색할 때 격자를 반드시 행 단위로만 분리해야 하는 걸까 ?
사실 발상1의 풀이와 코드가 복잡해지는 가장 큰 원인은 격자를 행 단위로 분리했을 때 비트마스크 계산이 복잡하기 때문이다.
격자판을 행 단위가 아닌 셀 단위로 분리할 수 없을까 ?
이전 풀이에서 격자를 행단위로 분리하는 이유는 그 다음 행을 탐색할 때 블럭을 겹치지 않게 배치하기 위해서이다.
즉, 분리의 단위가 중요한 것이 아니라 다음 위치에 배치할 때 영향을 줄 수 있는 위치들의 배치를 저장하고 다음 탐색에서 참고할 수 있도록 하는 것이 중요한 것이다.
행 단위로 분리하지 않고 셀 단위로 분리해도 이것이 가능하다.
아래 그림을 보자.
녹색 화살표의 방향대로 파란색 동그라미 위치까지 탐색했을 때, 다음에 탐색할 위치에 영향을 주는 칸은 빨간색 마름모위치 뿐이다. 저 위치에 블럭이 서있는지, 누워있는지 비트마스크로 저장하면 이전 풀이와 동일하게 풀이가 가능하다. 한칸 진행할 때마다 비트마스크의 가장 낮은 자리수를 검사하고 새로운 마스크를 자리에 추가하면 문제를 해결할 수 있다. 이 풀이가 이전 풀이보다 나은 점은 블럭이 현재 위치에서 누워있든 서있든 비트마스크를 좀 더 간편하게 계산할 수 있다는 점이다. 행 단위로 계산할 때는 이미 정해진 비트 마스크의 정합성을 검사하는 방식이었기 때문에 코드도 복잡하고 구조적으로 같은 비트마스크를 여러번 계산하게되는 문제가 있었다.
점화식2
코드2
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, m;
vector<vector<vector<int>>> dp;
const int mod = 9901;
int r(int x, int y, int st) {
if (y == m) { // 마지막 칸에 도달한 경우
if (x == n - 1) return 1; // 마지막 줄인 경우, 끝까지 탐색한 것이므로 경우의 수 1가지로 취급
else return r(x + 1, 0, st); // 그게 아니면 다음 줄 가기
}
int& ret = dp[x][y][st];
if (ret != -1) return ret;
if (st % 2 == 1) { // 발 밑 블럭이 서있으면 해당 칸 스킵
return ret = r(x, y + 1, st / 2); // 가장 오래된 비트마스크 제거
}
int s1 = 0, s2 = 0;
if (x < n - 1) { // 서있는 블럭은 마지막 줄에는 배치 불가
s1 = r(x, y + 1, st / 2 + (1 << (m - 1))); // 가장 오래된 비트마스크를 제거하고 최신 비트마스크에 서있는 블럭 표시
}
if (y < m - 1 && (st / 2) % 2 == 0) { // 눕는 블럭은 2칸 검사
s2 = r(x, y + 2, st / 4); // 눕는 블럭은 2칸 나아가므로 비트마스크 2칸 제거
}
return ret = (s1 + s2) % mod;
}
int main() {
cin >> n >> m;
dp = vector<vector<vector<int>>>(n + 1, vector<vector<int>>(m + 1, vector<int>((1 << m) + 1, -1)));
cout << r(0, 0, 0);
return 0;
}