그리디를 이용한 문제이다. 이 문제의 키포인트는 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;
}