첫 줄에서 스위치를 누를수 있는 모든 경우 (1024가지)를 미리 정해놓고
두번째 줄부터 이전 줄의 전구의 켜짐 상태를 그리디하게 끄면서 마지막 줄에 켜진 전구의 유무로 경우의 수를 구하는 문제
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <memory.h>
#include <math.h>
#define INF (10001)
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
int nx[5] = { 0,0,0,-1,1 };
int ny[5] = { 0,-1,1,0,0 };
char map[11][11];
char tmp[11][11];
void click(int x, int y) {
for (int i = 0; i < 5; i++) {
int _x = x + nx[i];
int _y = y + ny[i];
if (_x < 0 || _y < 0 || _x >= 10 || _y >= 10) {
continue;
}
tmp[_x][_y] = (tmp[_x][_y] == '#' ? 'O' : '#');
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
for (int i = 0; i < 10; i++) {
cin >> map[i];
}
int ans = INF;
for (int init = 0; init < 1024 ; init++) {
// map 복사
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
tmp[i][j] = map[i][j];
}
}
// 초기 값설정
int cnt = 0;
for (int i = 0; i < 10; i++) {
if (init & (1 << i)) {
cnt += 1;
click(0, i);
}
}
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 10; j++) {
if (tmp[i][j] == 'O') {
click(i + 1, j);
cnt += 1;
}
}
}
int flag = 1;
for (int i = 0; i < 10; i++) {
if (tmp[9][i] == 'O') {
flag = 0;
break;
}
}
if (flag) ans = min(ans, cnt);
}
cout << (ans != INF ? ans : -1);
}
반응형
'Solved.ac > Class 5' 카테고리의 다른 글
[BOJ] 백준 11437번: LCA (2) | 2020.09.22 |
---|---|
[BOJ] 백준 2467번: 용액 (1) | 2020.09.22 |
[BOJ] 백준 2098번: 외판원 순회 (0) | 2020.06.25 |
[BOJ] 백준 1509번: 팰린드롬 분할 (0) | 2020.06.25 |