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

https://www.acmicpc.net/problem/2138

2138번: 전구와 스위치

---

그리디 도장깨기 중 찾은 문제.

 

전구의 수는 최대 100'000개. 나올 수 있는 모든 경우의 수는 2^100'000..

당연히 무지성 브루트포스로는 안풀리는 문제이다. 

 

일단 비슷한 문제를 종만북에서 봤던 것 같다.

흐릿하지만 그 기억을 잘 떠올려서 문제를 접근하면.. 

문제를 푸는 데 가장 중요한건 스위치를 누르는 순서는 상관없다는 점.

1번을 누르고 2번을 누르든, 2번을 누르고 1번을 누르든 전구의 상태는 달라지지 않는다.

 

따라서 앞에서부터 차례대로 스위치를 누른다고 했을때, 지금까지 지나온 지점들 즉, 현재위치에서 스위치를 눌러도 바뀌지 않은 이전의 인덱스들은 모두 만들고자하는 전구의 상태와 동일해야 한다. 

 

위를 토대로, 현재상태를 bef, 목표를 aft라고 할때

bef[i]!=aft[i]일때 toggle해주면 되겠군! 했지만,

그렇게 하면 예제 출력이 되지않는다!

예제는 모든 칸을 toggle해야 답이 나오는데, 위의 방식은 첫번째 인덱스에서 toggle하지않기때문이다.

 

그래서 생각했던게... "첫번째꺼는 따로 처리해줘야되나?"

첫번째 스위치를 누른 경우와 누르지 않은 경우로 나누어서 위의 방법대로 돌려봐야 되나?싶었다.

그리고 됐다?

 

a에는 첫번째스위치를 누르지 않은 경우, b에는 첫번째 스위치를 누른 경우에 대한 정답을 저장한다.

각각의 경우에서 만들고자하는 상태에 도달하지 못하면 음수의 대충 큰 수를 넘겨주었다. 

이후 a,b로 정답을 잘 출력해주었다.

 

#include<bits/stdc++.h>
using namespace std;
#define X first 
#define Y second
#define rep(i,x,y) for(ll i=x;i<y;i++)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
/*------------------------------*/


int n;
string bef,aft;
void toggle(int i){
    if(i<0 || i>=n) return;
    bef[i] = "10"[bef[i]-'0'];
}
int func(){
    string tmp = bef;
    int cnt = 0;
    for(int i=1;i<n;i++){
        if(bef[i-1]!=aft[i-1]){
            cnt++;
            toggle(i-1); toggle(i); toggle(i+1);
        }
    }
    swap(tmp,bef);
    if(tmp!=aft) return -1e9;
    return cnt;

}
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>bef>>aft;

    int a = func();
    toggle(0); toggle(1);
    int b = func()+1;
    if(a+b < -1e9) cout<<-1<<'\n';
    else if(a+b<0) cout<<max(a,b)<<'\n';
    else cout<<min(a,b)<<'\n';

}

 

여기서 toggle 함수에서

bef[i] = "10"[bef[i]-'0'];

이런 문법을 코포 풀면서 처음 봤었는데

조건문 안쓰고 0은 1로, 1은 0으로 바꾸는 게 되게 신선한 충격이었다..

 

그때 충격이 머릿속에 깊이 박혀서.. 문제풀면서 요긴하게 쓰고있는 문법이다ㅎㅎ..