BOJ 2138 : 전구와 스위치

• 문제 링크 : boj.kr/2138
• 난이도 : G4
• 태그 : 그리디

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int check(string temp, string target) {
    int n = temp.size();
    int cnt = 0;
    for(int i = 1; i < n-1; i++) {
        if(temp[i-1] != target[i-1]) {
            temp[i-1] ^= 1;
            temp[i] ^= 1;
            temp[i+1] ^= 1;
            cnt++;
        }
    }
    if(temp[n-2] != target[n-2] && temp[n-1] != target[n-1]) {
        return cnt+1;
    }
    else if(temp[n-2] == target[n-2] && temp[n-1] == target[n-1]) {
        return cnt;
    }
    else {
        return n+1;
    }
}

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

    int n;
    cin >> n;
    string curr, target;
    cin >> curr >> target;

    int ans = check(curr, target);
    curr[0] ^= 1;
    curr[1] ^= 1;
    ans = min(ans, check(curr, target)+1);
    if(ans > n) cout << -1;
    else cout << ans;

    return 0;
}

---

풀이

첫 스위치를 누르는 경우, 누르지 않는 경우로 나누고 그리디하게 스위치를 누른다.

첫 스위치를 제외하면 1번째 전구에 영향을 줄 수 있는 스위치는 2번째 스위치밖에 없다.

2번째 스위치까지 누른 상태에서 2번째 전구에 영향을 줄 수 있는 스위치는 3번째 스위치밖에 없다.

확장하여 k번째 스위치까지 누른 상태에서 k번째 전구에 영향을 줄 수 있는 스위치는 k+1번째 스위치밖에 없다.

따라서 첫 스위치를 누르는 경우에 따라서 상황을 나누면 나머지는 확정된다.