백준 2138번 전구와 스위치 C++

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

 

맨 앞의 전구부터 순차적으로 만약 자기보다 앞에 있는 전구가 목표로 하는 상태와 같으면 누르지 않고 다음 전구로 넘어가고, 만약 다르다면 스위치를 눌러서 상태를 같게 만들어준 뒤 다음 전구로 넘어가는 방식으로 문제를 해결하였다.

 

여기서 주의해야할 점은 맨 앞의 전구는 자기보다 앞에 있는 전구가 없어서 비교가 불가능하기 때문에 맨 앞에 있는 전구를 눌렀을 때와 안눌렀을 때 이 두 경우를 모두 조사해야 한다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

int n;
string str, str_Push_First, target;
bool isPossible = false;
int ans = 987654321;

void Switch_On(int index, int num) {
	for (int i = index - 1; i < index - 1 + num; i++) {
		if (str[i] == '0') {
			str[i] = '1';
		}
		else {
			str[i] = '0';
		}
	}
}

void Solve(int index, int cnt) {
    //마지막 전구에 도달했을 때
	if (index == n - 1) {
		if (str[index - 1] == target[index - 1] && str[index] == target[index]) {
			ans = min(ans, cnt);
			return;
		}
		else {
			Switch_On(index, 2); //마지막 전구여서 2개만 바꿔준다
			cnt++;
			if (str[index - 1] == target[index - 1] && str[index] == target[index]) {
				ans = min(ans, cnt);
				return;
			}
			else return;
		}
	}
    //한칸 앞의 전구가 목표 상태와 같을때
	if (str[index - 1] == target[index - 1]) {
		Solve(index + 1, cnt);
	}
    //다를때
	else {
		Switch_On(index, 3); //스위치를 켜서 3개의 상태를 바꾼다
		Solve(index + 1, cnt + 1);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	cin >> str >> target;
	str_Push_First = str;
	for (int i = 0; i < 2; i++) {
		if (str_Push_First[i] == '0') {
			str_Push_First[i] = '1';
		}
		else {
			str_Push_First[i] = '0';
		}
	}
	Solve(1, 0);
	str = str_Push_First;
	Solve(1, 1);
	if (ans == 987654321) cout << -1;
	else cout << ans;
};