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

[ BOJ ] 2138번 : 전구와 스위치

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

---

[  문제  ]

N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 있는 전구는 켜지고, 켜져 있는 전구는 꺼지게 된다. 1번 스위치를 눌렀을 경우에는 1, 2번 전구의 상태가 바뀌고, N번 스위치를 눌렀을 경우에는 N-1, N번 전구의 상태가 바뀐다.

N개의 전구들의 현재 상태와 우리가 만들고자 하는 상태가 주어졌을 때, 그 상태를 만들기 위해 스위치를 최소 몇 번 누르면 되는지 알아내는 프로그램을 작성하시오.

[  입력  ]

첫째 줄에 자연수 $N$(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 전구들의 현재 상태를 나타내는 숫자 N개가 공백 없이 주어진다. 그 다음 줄에는 우리가 만들고자 하는 전구들의 상태를 나타내는 숫자 N개가 공백 없이 주어진다. 0은 켜져 있는 상태, 1은 꺼져 있는 상태를 의미한다.

[  출력  ]

첫째 줄에 답을 출력한다. 불가능한 경우에는 -1을 출력한다.

---

[  문제 접근 및 풀이  ]

i번째 스위치를 누르면 i-1, i, i+1의 전구가 바뀌기 때문에 가장 왼쪽에 있는 전구의 상태만

만들고자 하는 상태와 비교한다면 스위치를 누를지 말지 선택할 수 있다.

이를 재귀로 코드를 짜게 된다면 최대 $2^{n}$이 걸릴 수 있다. N은 최대 10만이기에

$2^{100000}$이라면 TLE가 날 수도 있기에 0과 1로 반전이 편하기도 한

C++ STL에 있는 bitset을 사용했다.

가장 왼쪽에 있는 1번 전구가 꺼진 상태, 켜진 상태로 함수에 넣고

2번 전구부터 자기 왼쪽에 있는 전구가 켜져야 하는지 꺼져야 하는지에 따라

자기 전구의 스위치를 누르면 $O(n)$에 구할 수 있다.

[  소스 코드  ]

#include<bits/stdc++.h>
using namespace std;
int N,MAXCNT=1234567890;
bitset<100002> S,RET,COPY;
void Switch1(int cnt,int idx);
void Q_2138();
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	Q_2138(); 
}
void Q_2138(){ //1번째 전구의 스위치를 누를지 말지를 기준으로
    // i-1번째 전구의 스위치를 누를지 말지 선택하기
    cin >> N;
    cin >> S;
    cin >> RET;
    //COPY는 스위치 누르기. S는 스위치 누르지 않기
    COPY=S;
    COPY.flip(N-1);
    COPY.flip(N-2);
    Switch1(0,N-2); //첫 전구의 스위치를 누른 경우
    S=COPY;
    Switch1(1,N-2); //첫 전구의 스위치를 누른 경우
    if(MAXCNT==1234567890) cout<<-1;
    else cout<< MAXCNT;
}
void Switch1(int cnt,int idx){//얼마나 스위치를 눌렀는가,idx가 어디인가.
    int counting=cnt;
    for(int i=idx;i>=0;i--){
        if(S[i+1]!=RET[i+1]){ // i-1번째의 전구가 맞추려는 상태와 다른 경우 눌러주기
            for(int j=0;j<3;j++){ 
                if(i-1+j <0) continue;
                S.flip(i-1+j);
            }
            counting++;
        }
    }
    string TEMP1=S.to_string();
    string TEMP2=RET.to_string();
    if(!TEMP1.compare(TEMP2)) MAXCNT=min(MAXCNT,counting); 
    //비교 후 전구들이 모두 같으면 최솟값 비교하기
}

---

 

PS. 이 문제는 1차원 배열의 문제이고 14939번 문제나 14927번 문제는 2차원 배열의 문제이므로 풀어보길 추천한다.