그냥 마음놓고 아무생각없이 backtracking으로 짰다가 시간초과를 맞은 문제.
처음엔 한 row마다 전부 A혹은 B로 바꾸는데 배열을 순회하며 O(W)의 시간이 걸리도록 짰지만.. 이를 더 빠르게 처리할 방법을 생각하다 포기했다가.. 알고리즘 관련 책을 뒤져보니 backtracking시 시간초과가 난다면 bitmasking을 이용하면 될 수도 있다는 문구를 보고 곰곰히 생각해봤다.
한 row를 bit로 표현하면 A, B로 바꿀때 O(1)로 줄일수 있다!!
이를 이용해 문제를 다시 풀었고 AC를 받아냄..ㅠㅠ 전체 시간은 O(w*d*3^d)
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#define INF 2e8
using namespace std;
int D, W, K;
int CheckArr[21];
bool Check();
int Count[1 << 13];
int solve(int row);
int main()
{
int T;
scanf("%d", &T);
//bit counting
for (int i = 0; i < (1 << 13); i++)
{
int z = i;
int maxS = 0;
int sum = 0;
while (z != 0)
{
if ((z & 1) == 1)
{
sum += 1;
}
else
{
maxS = max(maxS, sum);
sum = 0;
}
z /= 2;
}
maxS = max(maxS, sum);
Count[i] = maxS;
}
for (int t = 1; t <= T; t++)
{
int ans = 0;
memset(CheckArr, 0, sizeof(int) * 21);
scanf("%d %d %d", &D, &W, &K);
for (int i = 1; i <= D; i++)
{
for (int j = 1; j <= W; j++)
{
int tmp;
scanf("%d", &tmp);
if(tmp != 0)
CheckArr[i] |= (1<<(W-j));
}
}
ans = solve(1);
printf("#%d %d\n", t, ans);
}
return 0;
}
int solve(int row)
{
//기저조건 다 칠했을 때
if (row == D + 1)
{
if (Check())
return 0;
else
return INF;
}
//안칠하는 경우
if (Check())
return 0;
int ans = INF;
ans = min(ans, solve(row + 1));
//case1 A로 바꾸는 경우
int origin = CheckArr[row];
CheckArr[row] = 0;
ans = min(ans, solve(row + 1) + 1);
CheckArr[row] = origin;
//case2 B로 바꾸는 경우
CheckArr[row] |= ((1 << W)-1);
ans = min(ans, solve(row + 1) + 1);
CheckArr[row] = origin;
return ans;
}
bool Check()
{
bool check = true;
bool checkA = true;
bool checkB = true;
for (int k = 1; k <= W; k++)
{
int tmp = 0;
checkA = true;
checkB = true;
for (int r = 1; r <= D; r++)
{
int current = (CheckArr[r] >> (k - 1)) & 1;
tmp |= (current << (r-1));
}
if (Count[tmp] < K)
checkA = false;
int tmp2 = (~tmp) & ((1 << D) - 1);
if (Count[tmp2] < K)
checkB = false;
if (!checkA && !checkB)
{
check = false;
break;
}
}
return check;
}