[백준 2138번/c++] 전구와 스위치

알고리즘

• 그리디 알고리즘

 

---

풀이

1. 0번째 스위치를 누르는 경우와 0번째 스위치를 누르지 않는 경우를 나누어 생각한다.
2. 1~n-1번째 스위치를 누를지 말지 여부를 결정하기 위해 for문을 돌린다.
   1. i번째 스위치를 누를지 말지를 결정하기 위해 i-1번째 전구의 상태와 목표로 하는 i-1번째 전구의 상태를 비교한다.
      1. 같으면  누르고 cnt++
      2. 다르면 누르지 않는다.
3. 현재 전구의 상태와 목표로 하는 전구의 상태가 같으면 cnt를 리턴하고 그렇지 않으면 2147000000을 리턴한다.
4. 0번째 스위치를 누르는 경우와 0번째 스위치를 누르지 않는 경우 중 최소값을 골라 출력한다. 만약에 두 경우 모두 답이 나오지 않아 리턴값이 2147000000인 경우 -1을 출력한다.

 

---

전체 코드

#include <iostream>
#include <cstring>
using namespace std;

int n;
string current, target;

void press(int idx){
    for(int i=idx-1; i<=idx+1; i++){
        if(i<0 || i>n) continue;
        else{
            if(current[i]=='0') current[i]='1';
            else current[i]='0';
        }
    }
}

int check(bool state){
    int cnt=0;
    // 0번째 스위치
    if(state){
        press(0);
        cnt++;
    }

    // 1~n-1번째 스위치
    for(int i=1; i<n; i++){
        if(current[i-1]!=target[i-1]){
            press(i);
            cnt++;
        }
    }

    if(current==target) return cnt;
    else return 2147000000;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    freopen("input.txt", "rt", stdin);
    
    int ans, case1, case2;
    string c;
    cin >> n >> c >> target;
    current=c;
    // 0번째 스위치 누르는 경우
    case1=check(true);
    current=c;
    // 0번째 스위치 누르지 않는 경우
    case2=check(false);
    if(case1==2147000000 && case2==2147000000){
        cout << -1;
    } else{
        cout << min(case1, case2);
    }

    return 0;
}