14939 불 끄기 https://www.acmicpc.net/problem/14939
N*N 크기의 전구 상태가 주어진다.
모든 전구를 끌때 필요한 횟수를 구하는 문제다.
각각 홍익대, 서강대 플밍 경시대회에 나온 문제다.
시기도 비슷했는데 똑같은 문제가 나왔다.
전구문제만 보면 극혐하는데 (Condition of deep sleep) 고민하다가 힌트를 보고 풀게됬다.
첫행의 전구를 반전시킬 수 있는 경우에는 $2^N$만큼의 경우가 존재한다.
두번째 행부터는 앞서 나온 경우에서 윗행을 꺼야 넘어갈 수 있는 것이 자명하기때문에
윗행을 꺼주는 한가지 경우만 시행해주면 된다.
이렇게 쭉 가다가 N-1 행을 꺼줄 수 있으면 답이 존재하는 것이다.
풀고나서 삼성 S/W 역량테스트에 나올 만한 문제라고 생각됬다.
알고리즘과 적절한 구현력을 평가하기 좋은 문제이기 때문이다.
이번 교내 경시대회 문제가 꽤 괜찮은데 남은 문제도 풀어봐야겠다.
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int N;
int map[19][19];
int rowInfo[19];
vector<pair<int,int>> v;
int ans = 0x3f3f3f3f;
void init(int idx, int info, int cnt) {
if (idx == N) {
v.push_back({ info, cnt });
return;
}
init(idx + 1, info | (1 << idx), cnt + 1);
init(idx + 1, info, cnt);
}
void solve(int y, int prev, int here, int cnt) {
if (y == N) {
if (prev == 0 && cnt < ans) ans = cnt;
return;
}
if (y == 0) {
for (auto &i : v) {
int nprev = rowInfo[y];
int nhere = rowInfo[y + 1];
for (int n = 0;n < N;n++) {
if (i.first &(1 << n)) {
if (n - 1 >= 0) nprev ^= (1 << (n - 1));
if (n + 1 < N) nprev ^= (1 << (n + 1));
nprev ^= (1 << n);
nhere ^= (1 << n);
}
}
solve(y + 1, nprev, nhere, cnt + i.second);
}
}
else {
int nprev = here;
int nhere = rowInfo[y + 1];
int ncnt = 0;
for (int n = 0;n < N;n++) {
if (prev &(1 << n)) {
ncnt++;
if (n - 1 >= 0) nprev ^= (1 << (n - 1));
if (n + 1 < N) nprev ^= (1 << (n + 1));
nprev ^= (1 << n);
nhere ^= (1 << n);
}
}
solve(y + 1, nprev, nhere, cnt + ncnt);
}
}
int main() {
scanf("%d", &N);
for (int n = 0;n < N;n++) for (int m = 0;m < N;m++) {
scanf("%d", &map[n][m]);
if (map[n][m]) rowInfo[n] |= (1 << m);
}
init(0, 0, 0);
solve(0, 0, 0, 0);
printf("%d\n", ans == 0x3f3f3f3f ? -1 : ans);
return 0;
}
| cs |
