[2138] 전구와 스위치

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

2138번: 전구와 스위치

<문제>

순서를 강제하여 왼쪽부터 차례대로 켠다고 생각해보면, i-1이 목표와 다를때는 항상 i번 스위치를 눌러야한다.

이를 적용하기 위해서, 0번째 스위치를 키고 시작한 경우와 그렇지 않은경우, 2가지로 나눈 뒤

[1, n)까지 그리디의 논리를 전개시키면 되겠다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, cnt, ans = INT_MAX;
string cur, tar, base;
void toggle(int idx) {
    if (base[idx] == '1')
        base[idx] = '0';
    else
        base[idx] = '1';
}
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    cin >> cur;
    cin >> tar;
    int i;
    base = cur;
    for (i = 1; i < n; i++) {
        if (base[i - 1] != tar[i - 1]) {
            cnt++;
            toggle(i - 1);
            toggle(i);
            toggle(i + 1);
        }
    }
    if (base == tar) ans = min(cnt, ans);
 
    base = cur;
    toggle(0);
    toggle(1);
    cnt = 1;
    for (i = 1; i < n; i++) {
        if (base[i - 1] != tar[i - 1]) {
            cnt++;
            toggle(i - 1);
            toggle(i);
            toggle(i + 1);
        }
    }
    if (base == tar) ans = min(cnt, ans);
    if (ans == INT_MAX)
        cout << -1;
    else
        cout << ans;
    return 0;
}