[Boj] 백준 C++ #2138 전구와 스위치

📍 문제 링크 : https://www.acmicpc.net/problem/2138

 

📍 알고리즘 분류 : 그리디 알고리즘

 

📍 문제 풀이

 

신기한 점이 어떤 전구를 먼저 켜고 끄든, 순서가 중요하지 않다는 것이다!

따라서 우리는 첫 번째 전구부터 순서대로 탐색하면 된다. 그리디하게. 현재에 최적이 되도록.

첫 번째 전구를 목표 상태와 비교하고 다르다면 전구의 상태를 바꾸고, 같다면 그냥 두면 된다.

 

그런데 전구는 자신의 왼쪽, 자신, 자신의 오른쪽 이렇게 3개의 전구의 상태에 영향을 미치게 되는데

그리디하게 접근할 경우 이 조건이 훨씬 쉽게 만들어진다. 현재 보고 있는 i번째 전구를 변경하고자 할 경우 할 수 있는 것은 i+1번째 전구를 누르는 것이라는 것이다! i-1번째 전구나 i번째 전구를 누르면 안되는 이유는 아래 그림에 작성해두었다. 그리디 알고리즘에 의해 앞 전구들의 상태는 더 이상 바뀌면 안되기 때문이다. 

 

그래서 아래와 같이 정리할 수 있다. 

• i 번째 전구의 상태가 목표와 같다 = 아무것도 하지 않음
• i 번째 전구의 상태가 목표와 다르다 = i+1번째 전구를 누름

 

그런데 하나 따로 처리해주어야 하는 것이, 첫 번째 전구이다.

첫 번째 전구가 (목표와) 같은 상태일때, 아무것도 하지 않아도 되지만 첫 번째 전구와 두 번째 전구 둘 다 눌러도 된다.

그리고 첫 번째, 혹은 두 번째 둘다 바꿔주고자 한다면 첫 번째만 눌러도 되고, 두 번째만 눌러도 된다.

이 시작 부분에서 차이가 발생한다.

따라서 첫 번째 전구에 따라 시작을 달리하면 스위치 누르는 최소 횟수가 달라질 수 있다. 다 해보고 가장 최솟값을 답으로 도출하면 된다.

 

 

📍 소스 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

void press(int n, int idx, vector<int>& input){
    if(idx == 0){
        input[idx] = !input[idx];
        input[idx+1] = !input[idx+1];
    }else if(idx == n-1){
        input[idx-1] = !input[idx-1];
        input[idx] = !input[idx];
    }else{
        input[idx-1] = !input[idx-1];
        input[idx] = !input[idx];
        input[idx+1] = !input[idx+1];
    }
}

int solve1(int n, vector<int> input, vector<int>& target){
    //0번째, 1번째 버튼 누르지 않음
    int cnt = 0;
    for(int i=2;i<n-1;i++){
        if(input[i-1]!=target[i-1]){
            press(n, i, input);
            cnt++;
        }
    }
    if(input != target){
        return -1;
    }
    return cnt;
}

int solve2(int n, vector<int> input, vector<int>& target){
    //0번째, 1번째 누름
    press(n,0,input);
    press(n,1,input);
    int cnt = 2;
    for(int i=2;i<n;i++){
        if(input[i-1]!=target[i-1]){
            press(n, i, input);
            cnt++;
        }
    }
    if(input != target){
        return -1;
    }
    return cnt;
}

int solve3(int n, vector<int> input, vector<int>& target){
    //0번째만 누름
    press(n,0,input);
    int cnt = 1;
    for(int i=2;i<n;i++){
        if(input[i-1]!=target[i-1]){
            press(n, i, input);
            cnt++;
        }
    }
    if(input != target){
        return -1;
    }
    return cnt;
}

int solve4(int n, vector<int> input, vector<int>& target){
    //1번째만 누름
    press(n,1,input);
    int cnt = 1;
    for(int i=2;i<n;i++){
        if(input[i-1]!=target[i-1]){
            press(n, i, input);
            cnt++;
        }
    }
    if(input != target){
        return -1;
    }
    return cnt;
}

int main(){
    int n; cin>>n;
    string a,b;
    cin>>a>>b;
    vector<int> input(n,0);
    vector<int> target(n,0);

    for(int i=0;i<n;i++){
        input[i]=a[i]-'0';
        target[i]=b[i]-'0';
    }

    int ans;
    if(input[0]==target[0]){
        int tmp1 = solve1(n,input,target);
        int tmp2 = solve2(n,input,target);
        if(tmp1 == -1 && tmp2 == -1){
            ans = -1;
        }else if(tmp1 == -1){
            ans = tmp2;
        }else if(tmp2 == -1){
            ans = tmp1;
        }else{
            ans = min(tmp1, tmp2);
        }
    }else{
        int tmp1 = solve3(n,input,target);
        int tmp2 = solve4(n,input,target);
        if(tmp1 == -1 && tmp2 == -1){
            ans = -1;
        }else if(tmp1 == -1){
            ans = tmp2;
        }else if(tmp2 == -1){
            ans = tmp1;
        }else{
            ans = min(tmp1, tmp2);
        }
    }


    cout<<ans<<endl;
}

 

진짜 어렵ㄷ ㅏ.... ㅠ ㅠ ...... 사실 아직도 잘 못풀겠다...