백준 2138 전구와 스위치 (C++)

2138번: 전구와 스위치

그리디를 이용한 문제이다. 이 문제의 키포인트는 i==0일 때 상태를 바꾸냐 안 바꾸냐이다. 현재 위치를 i라고 한다면 i의 상태를 바꾸면 i-1과 i+1의 상태가 바뀌게 된다. 그렇기에 i-1의 상태를 바꿀려면 i를 바꾸어주면 된다. 반복문이 i=1에서 시작하기에 i=0일 때 상태를 바꾸냐 안바꾸냐로 나누어 반복문을 진행해주었다. 생각보다 어려운 문제였다. 아이디어가 떠오르지 않아 블로그들을 참고하여 풀었다. 참 어떻게 생각해냈는지 신기하다...

#include <iostream>
#include <algorithm>

using namespace std;

int N, result = 987654321;
string s1, s2;

string changeStatus(string s, int n) {
	s[n] = s[n] == '0' ? '1' : '0';
	if (n - 1 >= 0) 
		s[n - 1] = s[n - 1] == '0' ? '1' : '0';
	if (n + 1 < s.size())
		s[n + 1] = s[n + 1] == '0' ? '1' : '0';

	return s;
}

void change(bool first) {
	string tmp = s1;
	int count = 0;

	if (first) {
		tmp = changeStatus(tmp, 0);
		count++;
	}

	for (int i = 1; i < tmp.size(); i++) {
		if (tmp[i - 1] == s2[i - 1]) continue;

		tmp = changeStatus(tmp, i);
		count++;
	}

	if (tmp == s2) result = min(result, count);
}

void solution() {
	change(true);
	change(false);

	result = result == 987654321 ? -1 : result;
	cout << result;
}

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

	cin >> N;
	cin >> s1;
	cin >> s2;

	solution();
	
	return 0;
}