BOJ2138 전구와 스위치(C++)

---

https://www.acmicpc.net/problem/2138

태그 : 그리디

---

사고 과정

https://www.acmicpc.net/problem/1080

문제를 읽자마자 생각난 문제이다. 바로 그리디하게 스위치를 누르면 되겠다고 생각했다.

처음에는 첫 전구가 다를 때 0번인덱스에서 뒤집는 경우 / 1번 인덱스에서 뒤집기 시작하는 경우

이런식으로 처리했다가 WA를 받았다.

그냥 0번에서 뒤집은 경우/뒤집지 않은 경우 각각 그리디하게 켜나가서 해결했다.

---

코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int n;
string a, b, c;
int ans;

void solve() {

	c = a;
	a[0] = (a[0] - '0') ? '0' : '1';
	a[1] = (a[1] - '0') ? '0' : '1';
	++ans;

	for (int i = 1; i < n - 1; ++i) {
		if (a[i - 1] != b[i - 1]) {
			a[i - 1] = (a[i - 1] - '0') ? '0' : '1';
			a[i] = (a[i] - '0') ? '0' : '1';
			a[i + 1] = (a[i + 1] - '0') ? '0' : '1';
			++ans;
		}
	}
	if (b[n - 2] != a[n - 2]) {
		a[n - 2] = (a[n - 2] - '0') ? '0' : '1';
		a[n - 1] = (a[n - 1] - '0') ? '0' : '1';
		++ans;
	}

	if (b[n - 1] != a[n - 1]) {
		ans = -1;
	}


	int tmp = 0;

	for (int i = 1; i < n - 1; ++i) {
		if (c[i - 1] != b[i - 1]) {
			c[i - 1] = (c[i - 1] - '0') ? '0' : '1';
			c[i] = (c[i] - '0') ? '0' : '1';
			c[i + 1] = (c[i + 1] - '0') ? '0' : '1';
			++tmp;
		}
	}
	if (b[n - 2] != c[n - 2]) {
		c[n - 2] = (c[n - 2] - '0') ? '0' : '1';
		c[n - 1] = (c[n - 1] - '0') ? '0' : '1';
		++tmp;
	}


	if (b[n - 1] != c[n - 1]) {
		tmp = -1;
	}
	if (ans != -1 || tmp != -1) {
		if (ans == -1) {
			ans = tmp;
		}
		else if (tmp == -1) {

		}
		else {
			ans = min(ans, tmp);
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n;

	cin >> a;
	cin >> b;

	solve();

	cout << ans;
}

---

후기

이 정도는 보자마자 그리디라고 떠올릴 수 있는 것 같다.

첫 분기를 너무 복잡하게 생각했던것이 흠이였다.

뒤집는 부분을 함수로 빼면 코드가 더 예쁠 것 같다.