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

문제

N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 있는 전구는 켜지고, 켜져 있는 전구는 꺼지게 된다. 1번 스위치를 눌렀을 경우에는 1, 2번 전구의 상태가 바뀌고, N번 스위치를 눌렀을 경우에는 N-1, N번 전구의 상태가 바뀐다.

N개의 전구들의 현재 상태와 우리가 만들고자 하는 상태가 주어졌을 때, 그 상태를 만들기 위해 스위치를 최소 몇 번 누르면 되는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 전구들의 현재 상태를 나타내는 숫자 N개가 공백 없이 주어진다. 그 다음 줄에는 우리가 만들고자 하는 전구들의 상태를 나타내는 숫자 N개가 공백 없이 주어진다. 0은 켜져 있는 상태, 1은 꺼져 있는 상태를 의미한다.

출력

첫째 줄에 답을 출력한다. 불가능한 경우에는 -1을 출력한다.

 

접근 방식

 

한 전구의 상태를 바꾸려면 그 전구의 바로 앞 전구에 대한 결정을 미리 해야 하는 것이 중요한 포인트다.

따라서, 첫 번째 전구에 대한 상태를 두가지로 나누어서 풀면된다.

첫번째 전구의 스위치를 누르느냐, 누르지 않느냐

이후로는 현재 전구가 목표 상태의 전구와 다르면 스위치를 누르고, 같다면 스위치를 누르지 않고 진행하면 된다..!

 

코드

 

#include <bits/stdc++.h>
using namespace std;

// 스위치 눌렀을 때 해당 인덱스와 좌우 전구를 반전하는 함수
void toggle(string &tmp, int idx) {
    for (int i = idx - 1; i <= idx + 1; i++) {
        if (i >= 0 && i < tmp.size()) {
            tmp[i] = (tmp[i] == '0') ? '1' : '0';
        }
    }
}

int main() {
    int n;
    cin >> n;
    string str, goal;
    cin >> str >> goal;

    int ans = INT_MAX;

    // 첫번째 전구를 누르지 않은 경우
    string tmp = str;
    int cnt = 0;
    for (int i = 1; i < n; i++) {
        if (tmp[i - 1] != goal[i - 1]) {
            toggle(tmp, i);
            cnt++;
        }
    }

    if (tmp == goal) ans = min(ans, cnt);

    // 첫번째 전구를 누른 경우
    tmp = str;
    cnt = 1; // 첫 번째 전구를 눌렀으므로 카운트를 1로 시작
    toggle(tmp, 0);

    for (int i = 1; i < n; i++) {
        if (tmp[i - 1] != goal[i - 1]) {
            toggle(tmp, i);
            cnt++;
        }
    }

    if (tmp == goal) ans = min(ans, cnt);

    if (ans == INT_MAX) cout << -1;
    else cout << ans;

   
}