백준 2138번 전구와 스위치✨✨

www.acmicpc.net/problem/2138

2138번: 전구와 스위치

IDEA

여태까지 풀어본 그리디 중에 제일 어려운 문제였던 거 같다...

아무리 고민을 해도 접근 방법을 못찾겠어서 다른 블로그들(staticvoidlife.tistory.com/143)을 참고했다. ㅜㅜ

 

최대 수가 100,000 이기 때문에 이중 for문 등 한 번 지나온 인덱스를 다시 돌아가서 보면 시간초과가 난다.

특정 인덱스 이전의 전구상태들을 목표 전구상태와 똑같이 만들어주면서 하나하나 진행하는 게 포인트같다.

이렇게 생각하면 1번째 스위치를 누르면 0번째 전구가 변하고, 2번째 스위치를 누르면 1번째 전구가 변한다.

0번째 전구부터 상태를 변경시켜 목표 전구상태와 일치시킨다고 생각해보면 1번째 스위치부터 누르게 된다. 

 

그래서 맨 처음에 1) 0번째 스위치를 눌렀을 때 , 2) 0번째 스위치를 누르지 않았을 때로 나눠서 생각해줘야한다.

 -> init1 , init2로 init2는 0번째 스위치를 눌렀다고 가정해 0번,1번 전구의 상태를 바꿔준다.

 

i번째 스위치를 누르기 전 i-1번째 전구가 목표전구의 상태와 같은 지 확인한다.

이미 같다면 아무 일 없이 i+1번째 스위치로 넘어간다. 

만약 다르다면 i-1 , i ,i+1 전구의 상태를 바꿔준 후, 스위치를 누른 횟수를 하나 카운팅해주고 그 다음 i+1번째 스위치로 넘어간다. 

인덱스가 n번째가 되면 n번째 스위치나 전구는 없기때문에 이전 전구들의 상태가 목표전구의 상태와 모두 같은 지 확인해준다. 

 

CODE

#include <iostream>
#include <vector>
#include<string>
#include<cmath>
#include<algorithm>
#include<stack>

using namespace std;
int n , answer = 1000000;

int target[1000001];

void switch_on (int init[] , int idx, int cnt) {
	if (idx == n ) {
		if (init[n - 1] == target[n - 1]) {
			answer = min(cnt, answer);
		}
		return;
	}
	if (init[idx - 1] == target[idx - 1]) switch_on(init, idx + 1, cnt);

	else {
		//i-1 ~ i+1 까지 바꿈
		init[idx - 1] == 0 ? init[idx - 1] = 1 : init[idx-1] = 0;
		init[idx] == 0 ? init[idx] = 1 : init[idx] = 0;
		init[idx + 1] == 0 ? init[idx +1] = 1 : init[idx+1] = 0;
		switch_on(init, idx + 1, cnt + 1);
	}
}

int main() {
	//cin.tie(NULL);
	//ios_base::sync_with_stdio(false);
	scanf("%d", &n);

	int init1[100001];
	int init2[100001];

	for (int i = 0; i < n; i++) {
		scanf("%1d", &init1[i]);
		init2[i] = init1[i];
	}
	for (int i = 0; i < n; i++) scanf("%1d", &target[i]);
	//init1 은 스위치 1번 안누른 상태 ,init2는 스위치 1번을 누른 상태 
	init2[0] == 0 ? init2[0] = 1 : init2[0] = 0;
	init2[1] == 0 ? init2[1] = 1 : init2[1] = 0;

	switch_on(init1 , 1 , 0);
	switch_on(init2, 1, 1);
	if (answer == 1000000) printf("-1");
	else printf("%d", answer);
}