[백준] 전구와 스위치 2138번 (c++) 그리디

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

 

풀이 방법

이 문제는 전구를 켜는 순서가 중요하지 않으며, 또한, 전구를 여러 번 켜고 끄더라도 같은 상태로 반복하므로, 각 전구는 0번 또는 1번만 변경하면 된다는 점을 파악하는 것이 중요하다. (2번 스위치 하는 것은 0번 스위치 하는 것과 동일)

 

문제 해결을 위해 첫 번째 전구부터 시작하여 전구를 바꾸는 경우와 그대로 두는 경우를 고려하며 탐색한다. 이 과정에서 현재 인덱스 이전의 전구가 원하는 정답 상태와 다르다면, 반드시 현재 전구를 바꿔야 한다는 규칙을 도출할 수 있다. 이러한 방식으로 인덱스를 늘려가며 조건을 적용해 나가면 최소 횟수로 전구를 원하는 상태로 만들 수 있다.

 

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int n, ans = 987654321;
string src, dst;
int arr[100001], goal[100001];


// 처음을 선택하냐 마냐를 고려하기

void turn_lamp(int idx) {
	arr[idx - 1] = (arr[idx - 1] + 1) % 2;
	arr[idx] = (arr[idx] + 1) % 2;
	if (idx + 1 < src.length()) arr[idx + 1] = (arr[idx + 1] + 1) % 2;
}

void init() {
	for (int i = 0; i < src.length(); i++) { // 램프 초기화
		if (src[i] == '0') arr[i] = 0;
		else arr[i] = 1;
	}
}

bool check() {
	for (int i = 0; i < src.length(); i++) {
		if (arr[i] != goal[i]) return false;
	}
	return true;
}
void sol() {
	// 1번을 선택했을 때, 2번이 다르다면 선택하면 안된다.

	// 이전 개 다르면 본인을 선택해야 한다. (무조건)
	// 이전 개 같다면 본인을 선택하면 안된다.(무조건)
	

	init();
	// 0번을 킨경우
	arr[0] = (arr[0] + 1) % 2;
	arr[1] = (arr[1] + 1) % 2;
	int cnt = 1;
	for (int i = 1; i < src.length(); i++) {
		if (arr[i - 1] != goal[i - 1]) {
			turn_lamp(i);
			cnt++;
		}
	}
	if (check()) ans = cnt;
	

	init();
	cnt = 0;
	// 0번을 안킨경우
	for (int i = 1; i < src.length(); i++) {
		if (arr[i - 1] != goal[i - 1]) {
			turn_lamp(i);
			cnt++;
		}
	}

	if (check()) ans = min(ans, cnt);
}

int main() {

	cin >> n;
	cin >> src >> dst;
	
	for (int i = 0; i < src.length(); i++) { // 램프 초기화
		if (dst[i] == '0') goal[i] = 0;
		else goal[i] = 1;
	}

	sol();

	if (ans == 987654321) cout << -1;
	else cout << ans << endl;
	return 0;
}