[ 백준 / C++ ] 2138 : 전구와 스위치

[ 문제 ]

 

2138번: 전구와 스위치

 

[ 접근방법 ]

 

i(1 < i < N)번 스위치를 누르면 i - 1, i, i + 1 세 개의 전구 상태가 바뀐다.

 

전구를 왼쪽부터 비교해가면서 진행해 나간다고 하자.

즉, 스위치를 왼쪽부터 순서대로 누른다고 하자.

 

(일단 1번 스위치 스킵), 만약 1번 전구 상태를 바꿔야 한다면, 유일하게 바꿀 수 있는 2번 스위치를 눌러야 한다.

2번 스위치를 누른 후에, 만약 2번 전구 상태를 바꿔야 한다면, 유일하게 바꿀 수 있는 3번 스위치를 눌러야 한다.

 

이런식으로 진행하면 O(N)만에 답을 구할 수 있다.

 

여기서 문제는 0번 전구가 없기 때문에 1번 스위치는 예외 처리를 해주어야 한다.

1번 스위치를 눌렀을 때와 아닐 때 두 경우에 대해 위의 과정을 진행해주면 마찬가지로 O(N)만에 답을 구할 수 있다.

 

[ 소스코드 ]

 

#include <iostream>

using namespace std;

int n, ans = -1, cnt;
string before, after, tmp;

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

    cin >> n >> before >> after;

    tmp = before;
    for(int i = 1; i <= tmp.size() - 1; i++){
        if(tmp[i - 1] != after[i - 1]){
            cnt++;
            for(int j = -1; j <= 1; j++){
                if(i + j < tmp.size()){
                    if(tmp[i + j] == '0'){
                        tmp[i + j] = '1';
                    }else{
                        tmp[i + j] = '0';
                    }
                }
            }
        }
    }
    if(tmp == after){
        ans = cnt;
    }

    tmp = before;
    cnt = 1;
    for(int i = 0; i <= 1; i++){
        if(tmp[i] == '0'){
            tmp[i] = '1';
        }else{
            tmp[i] = '0';
        }
    }
    for(int i = 1; i <= tmp.size() - 1; i++){
        if(tmp[i - 1] != after[i - 1]){
            cnt++;
            for(int j = -1; j <= 1; j++){
                if(i + j < tmp.size()){
                    if(tmp[i + j] == '0'){
                        tmp[i + j] = '1';
                    }else{
                        tmp[i + j] = '0';
                    }
                }
            }
        }
    }
    if(tmp == after){
        if(ans == -1){
            ans = cnt;
        }else{
            ans = min(ans, cnt);
        }
    }

    cout << ans;

    return 0;
}