C++ 백준 2138번

백준 2138번 www.acmicpc.net/problem/2138

2138번: 전구와 스위치

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

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

 

아까 푼 1080번이랑 비슷하게 생겨서 비슷한 아이디어로 가면 되겠지~~ 했다가 눈물 광광..

하나를 끄면 그 앞뒤 총 세개의 상태가 바뀐다. 그래서 케이스를 첫 번째 전구를 눌렀을 때/안 눌렀을 때로 나누고 생각해보면 이제 첫 번째 전구의 상태를 바꾸는 거는 2번 전구를 누르냐 안 누르냐에 달렸다. 그래서 뭐 2번 전구를 눌러서 1번 전구 상태를 바꿨다고 하면 이제 2번 전구의 상태는 3번 전구를 누르냐 안 누르냐에 달렸다!! 

이렇게 쭉쭉 가면 i-1번 전구의 상태는 i번 전구의 상태에 달린거니까 이렇게 다 진행했을 때 마지막 전구가 우리가 원하는 상태의 마지막 전구랑 같으면 된다!!(마지막 전구는 그 뒤에 전구가 없으니까 더 이상 상태를 바꿀 수 없음!! 1080번 아이디어 참고!! guiyum.tistory.com/48)

 

최대한 예쁘게 풀고 싶었는데 함수 쓸려니까 괜히 더 헷갈려서 그냥 노가다,, 로 풀었다ㅠㅠ

나중에 다시 예쁘게 풀어서 수정해야지ㅠㅠㅠㅠㅠ

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int a[100001]; // 첫번째 누른 경우
int ca[100001]; // 첫번째 안누른 경우
int b[100001]; // 목표 전구

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%1d", &a[i]);
		ca[i] = a[i];
	}
	for (int i = 0; i < n; i++) {
		scanf("%1d", &b[i]);
	}
	a[0] = 1 - a[0];
	a[1] = 1 - a[1]; // 첫번째 누른 경우
	int sum1 = 1;
	int sum2 = 0;
	for (int i = 1; i < n - 1; i++) {
		if (a[i - 1] != b[i - 1]) {
			for (int j = i - 1; j <= i + 1; j++) {
				a[j] = 1 - a[j];
			}
			sum1++;
		}
		else continue;
	}
	if (a[n - 2] != b[n - 2]) { // 마지막 바로 앞의 전구 따로 처리
		a[n - 2] = 1 - a[n - 2];
		a[n - 1] = 1 - a[n - 1];
		sum1++;
	}
	for (int i = 1; i < n - 1; i++) { // 첫번째 안누른경우
		if (ca[i - 1] != b[i - 1]) {
			for (int j = i - 1; j <= i + 1; j++) {
				ca[j] = 1 - ca[j];
			}
			sum2++;
		}
		else continue;
	}
	if (ca[n - 2] != b[n - 2]) { // 마지막 바로 앞의 전구 따로 처리
		ca[n - 2] = 1 - ca[n - 2];
		ca[n - 1] = 1 - ca[n - 1];
		sum2++;
	}
	bool ans1 = true;
	bool ans2 = true;
	for (int i = 0; i < n; i++) {
		if (a[i] != b[i]) {
			ans1 = false;
		}
		if (ca[i] != b[i]) {
			ans2 = false;
		}
	}
	if (ans1 && ans2) {
		printf("%d\n", min(sum1, sum2));
	}
	else if (ans1) {
		printf("%d\n", sum1);
	}
	else if (ans2) {
		printf("%d\n", sum2);
	}
	else printf("-1\n");
}