[BOJ/C++] 2138 전구와 스위치

문제

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

풀이

Greedy 문제 같긴한데 아이디어가 떠오르지 않아서 다른 사람 풀이를 참고했다.

• 각각의 스위치가 영향을 주는 전구
  

• 0번 스위치가 정해지면 0번 전구에 영향을 주는 건 1번 스위치 밖에 없음
  

• 1번 스위치가 정해지면 1번 전구에 영향을 주는 건 2번 스위치 밖에 없음
  

이렇게 끝까지 갔을 때, 최종적으로 만들고자 하는 전구 상태와 똑같은지 비교하면 된다.
0번 스위치를 누른 경우와 / 안 누른 경우 나눠서 실행해보면 된다. (나는 mark 변수를 인자로 넘겨서 조건 걸어줬다.)

코드

#include <iostream>
#include <string.h>
#include <cmath>
#define MAX 987654321

using namespace std;

int N;
string st, dt;
int ans = MAX;

void solve(int mark) {
	string tmp = st;
	int cnt = 0;
	if (mark == 0) { //0번 스위치 뒤집고 시작
		tmp[0] = (tmp[0] == '0') ? '1' : '0';
		tmp[1] = (tmp[1] == '0') ? '1' : '0';
		cnt++;
	}
	for (int i = 1; i < N; i++) {
		if (tmp[i - 1] != dt[i - 1]) {
			if (i - 1 >= 0) //(i-1) 스위치 변경
				tmp[i - 1] = (tmp[i - 1] == '0') ? '1' : '0';
			tmp[i] = (tmp[i] == '0') ? '1' : '0'; //i 스위치 변경
			if (i + 1 <= N - 1) //(i+1) 스위치 변경
				tmp[i + 1] = (tmp[i + 1] == '0') ? '1' : '0';

			cnt++;
		}
	}
	if (tmp == dt)
		ans = min(ans, cnt);
}

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

	cin >> N >> st >> dt;
	solve(0);
	solve(1);
	if (ans != MAX)
		cout << ans;
	else {
		cout << -1;
	}

	return 0;
}