[PS 백준 - 3.9] 2138번: 전구와 스위치

문제 정보

백준 2138번 - 바로가기

• 난이도: 실버 2
• 알고리즘: 그리디 알고리즘

---

코멘트

생각보다 어려웠다. 처음에 나도 모르게 브루트포스로 접근했다가, 10개짜리만 되도 프로그램이 무한 루프에 돌아서 틀려버렸다. 도저히 안되서 질문글의 블로그를 찾아서 아이디어를 얻을 수 있었다.

1. 전구 i번이 원하는 상태랑 동일하면 그대로 넘어가고, 다르면 i+1번 스위치를 누른다. (i=0부터 N-1까지)
2. 0번 스위치를 눌렀을 때, 누르지 않았을 때로 구분해서 각각 1번을 반복한다. 둘 다 가능한 케이스는 없기 때문에 둘 중 하나라도 되면 그 값을 출력하고, 둘 다 안되면 -1을 출력한다.

---

소스 코드

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

using namespace std;

int main() {
	std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

// ========================================
	int n;
	cin >> n;

	int* arr1 = new int[n];
	int* arr2 = new int[n];

	for (int i = 0; i < n; i++) {
		char c;
		cin >> c;
		arr1[i] = c - '0';
	}
	for (int i = 0; i < n; i++) {
		char c;
		cin >> c;
		arr2[i] = c - '0';
	}
// ========================================
	
	int cnt = 0;
	int result = -1;

	int* temp = new int[n];
	for (int i = 0; i < n; i++) temp[i] = arr1[i]; // 임시로 arr1 담을 배열

	// 먼저 0번 스위치 눌렀을 경우
	temp[0] = temp[0] == 0 ? 1 : 0;
	temp[1] = temp[1] == 0 ? 1 : 0;
	cnt++;

	// 0번 스위치 누르고 난 후 for문 돌리기
	for (int i = 1; i < n; i++) {
		if (i == n - 1) {
			if (temp[i-1] != arr2[i-1]) { // 다르면 스위치 누르기
				temp[i - 1] = temp[i - 1] == 0 ? 1 : 0;
				temp[i] = temp[i] == 0 ? 1 : 0;
				cnt++;
			}
		}
		else {
			if (temp[i-1] != arr2[i-1]) { // 다르면 스위치 누르기
				temp[i-1] = temp[i-1] == 0 ? 1 : 0;
				temp[i + 1] = temp[i + 1] == 0 ? 1 : 0;
				temp[i] = temp[i] == 0 ? 1 : 0;
				cnt++;
			}
		}
	}
	bool flag = true;

	for (int i = 0; i < n; i++) {
		if (temp[i] != arr2[i]) { // 다르면 결과 저장 안함
			flag = false;
			break;
		}
	}
	if (flag) result = cnt;

	// 초기화 작업
	cnt = 0;
	for (int i = 0; i < n; i++) temp[i] = arr1[i];

	// 0번 스위치 안 눌렀을 경우 바로 for문 돌리기
	for (int i = 1; i < n; i++) {
		if (i == n - 1) {
			if (temp[i - 1] != arr2[i - 1]) { // 다르면 스위치 누르기
				temp[i - 1] = temp[i - 1] == 0 ? 1 : 0;
				temp[i] = temp[i] == 0 ? 1 : 0;
				cnt++;
			}
		}
		else {
			if (temp[i - 1] != arr2[i - 1]) { // 다르면 스위치 누르기
				temp[i - 1] = temp[i - 1] == 0 ? 1 : 0;
				temp[i + 1] = temp[i + 1] == 0 ? 1 : 0;
				temp[i] = temp[i] == 0 ? 1 : 0;
				cnt++;
			}
		}
	}

	flag = true;

	for (int i = 0; i < n; i++) {
		if (temp[i] != arr2[i]) { // 다르면 결과 저장 안함
			flag = false;
			break;
		}
	}
	if (flag) result = cnt;
	
	cout << result;

	delete[] temp;
	delete[] arr1;
	delete[] arr2;
}