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

문제

2138번: 전구와 스위치

 

코드

#include <iostream>
#define INF 1e6
using namespace std;

int switch_first = 0, switch_second = 1 ;

bool check(string blub, string make, int seq){
    for(int i=1; i<blub.length(); i++){
        if(blub == make) return true;
        if(blub[i-1] != make[i-1]){
            blub[i-1]=='0'?blub[i-1]='1':blub[i-1]='0';
            blub[i]=='0'?blub[i]='1':blub[i]='0';
            blub[i+1]=='0'?blub[i+1]='1':blub[i+1]='0';
            if(seq==1) switch_first++;
            else switch_second++;
        }
    }
    if(blub == make) return true;
    return false;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int N; cin>>N;
    string blub, make; cin>>blub>>make;
    //0번 안눌렸을 때
    bool flag1 = check(blub, make, 1);
    if(!flag1) switch_first = INF;
    //0번 눌렸을 때
    blub[0]=='1'?blub[0]='0':blub[0]='1';
    blub[1]=='1'?blub[1]='0':blub[1]='1';
    bool flag2 = check(blub, make, 2);
    if(!flag2) switch_second = INF;
    
    if(switch_first == INF && switch_second == INF) cout<<-1;
    else cout<<min(switch_first, switch_second);
}

 

풀이

그리디 문제집을 통해 시작부터 그리디라는 사실을 인지하고 있었지만, 그렇지 않았다면 DP로 접근하다가 결국 못 풀었을 것 같았던 문제였습니다. 도저히 풀이 아이디어를 떠올리지 못해 아래 두 블로그의 글을 보고 해결했습니다.

1. https://burningjeong.tistory.com/409
2. https://staticvoidlife.tistory.com/143

문제 풀이 아이디어는 다음과 같습니다.

좌측의 전구는 신경 쓰지 않고, 현재 전구가 만들어야 하는 전구와 같은지를 비교합니다. 

1. 현재 인덱스의 전구가 만들어야 하는 인덱스의 전구와 같다면 넘어갑니다.
2. 만약 현재 인덱스의 전구가 만들어야 하는 인덱스의 전구와 다르다면 우측의 전구를 변경합니다.
3. 즉, 좌측의 전구는 신경쓰지 말고 현재 전구만 신경 써서 만든 다음 최종적으로 원하는 전구가 된다면 최솟값을 기록합니다.

따라서 0번 인덱스의 전구를 눌렀을때 와 누르지 않았을 때의 스위치의 최솟값을 출력하면 됩니다.