[2138] 전구와 스위치

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

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을 출력한다.

코드

#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <vector>

using namespace std;

int N;
vector<int> light;
vector<int> light2;
vector<int> temp;
int ans = 0;

bool checkAns(){
	for(int i=0; i<N; ++i){
		if(light[i] != light2[i]){
			return false;
		}
	}
	return true;
}

int turn(int a){
	if(a == 0){
		return 1;
	}
	else{
		return 0;
	}
}

int main(void){
	cin >> N;

	for(int i=0; i<N; ++i){
		int a;
		scanf("%1d", &a);
		light.push_back(a);
	}

	for(int i=0; i<N; ++i){
		int a;
		scanf("%1d",&a);
		light2.push_back(a);
	}

	temp = light;

	for(int i=1; i<N; ++i){
	// i-1번째 전구를 확인
		if(light[i-1] != light2[i-1]){
			ans++;
			light[i-1] = turn(light[i-1]);
			light[i] = turn(light[i]);
			if(i != N-1){
				light[i+1] = turn(light[i+1]);
			}
		}
	}

	if(checkAns()){
		cout << ans;
		return 0;
	}

먼저 N이 10^5이기 때문에 이중 반복문을 쓰면 시간 초과가 난다 때문에 O(nlogn)이나 O(n)의 해결 방법을 찾아야 하는데

이때 생각 할 수 있는게 그리디 방법이다.

이 문제에 그리디를 어떻게 적용할까 잘 생각해보면 전구의 순서대로 불을 조정하는 것이다.

무슨 뜻이냐 하면은 만약 첫번째나 마지막 전구 이외의 다른 전구 번호의 버튼을 누르면 i-1, i, i+1번의 전구들의 불이 바뀌게 된다.

이때, i-1번의 전구만 생각하면 된다. 

i-1번의 전구에 영향을 끼치는 건 i-2번 버튼, i-1번 버튼, i번 버튼이다. i+1번의 버튼은 i-1번 전구에 영향을 줄 수 없기 때문에 무조건 i번 버튼에서 i-1번의 전구 불이 알맞게 들어야 한다.

이를 좀 더 생각해보면 첫 번째 전구에 힌트가 있다.

첫번째 전구에 영향을 주는 버튼은 첫번째 전구와 두번째 전구가 있다.

즉, 첫번째 전구를 키는 경우와 키지 않는 경우를 나눌 수 있다.

이 두경우를 나눠 불을 켜보고 만약 그럼에도 답과 맞지 않는다면 -1을 출력한다.