[C++] BOJ(백준) 2138 전구와 스위치

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

2138번: 전구와 스위치

 

그리디 문제다.

 

스위치를 작동하는 가장 효율적인 방법은 순차적으로 탐색하되 지나간 전구는 건드리지 않는 것이다.

즉, n번째 전구를 바꾸기 위해서는 n+1번째 스위치를 작동하는 것이다.

 

이 방법으로 문제를 해결하려고 하면 첫 번째 스위치에 대한 의문이 생긴다.

첫 번째 스위치는 이전 전구가 존재하지 않으므로 작동 여부를 판별할 수 없다.

때문에 전구 탐색을 두 번 진행한다.

1. 첫 번째 스위치 작동 O

2. 첫 번째 스위치 작동 X

 

두 가지 경우의 스위치 작동 횟수를 구하고 최솟값을 출력하는 것이다.

 

마지막 스위치를 작동하기 위해서도 여러 방법이 떠올랐다.

1. n - 1 번째 인덱스까지만 반복문 돌리고 n번째는 따로 처리하기

2. 반복문 내 if 문으로 범위 검사하기

3. for문 조건에 함께 넣기

 

3번을 택했다. 조금 더 간결한 느낌

 

* 예외처리를 까먹어서 잠깐 헤맸다

 

#include <iostream>
using namespace std;

int n, re = 1000000;
string Q, A;

void solve(int zero) {
	string input = Q;
	int cnt = 0;

	// 첫 번째 스위치 작동 여부
	if (zero) {
		input[0] = input[0] == '1' ? '0' : '1';
		input[1] = input[1] == '1' ? '0' : '1';
		cnt++;
	}

	for (int i = 1; i < n; i++) {
		// 바로 이전 전구가 다르다면 스위치 작동
		if (input[i - 1] != A[i - 1]) {
			for (int j = i-1; j <= i + 1 && j < n; j++)
				input[j] = input[j] == '1' ? '0' : '1';
			cnt++;
		}
	}
	
	if (input == A) re = min(re, cnt);
}

int main() {
	cin >> n >> Q >> A;
	solve(0);
	solve(1);
	if (re == 1000000) cout << -1;
	else cout << re;
}

 

// 위 코드는 블로그 작성 겸 정리 겸 깔끔하게 다듬은 코드다.

생각나는대로 작성하고 제출했던 코드는 올릴까 말까 고민을 했는데

코드가 이렇게까지 더러울 수도 있구나... 겸 이런 코드가 깔끔해 지는구나... 겸 주석 없이 올린다.

 

#include <iostream>
using namespace std;

bool input[100000];
bool input2[100000];
bool output[100000];

int main() {
	int n;		cin >> n;
	string s;	cin >> s;

	for (int i = 0; i < n; i++) {
		input[i] = s[i] - '0';
		input2[i] = s[i] - '0';
	}

	cin >> s;
	for (int i = 0; i < n; i++)
		output[i] = s[i] - '0';


	int mini = 1;
	input[0] = input[0] ? false : true;
	input[1] = input[1] ? false : true;
	for (int i = 1; i < n - 1; i++) {
		if (input[i - 1] != output[i - 1]) {
			input[i - 1] = input[i - 1] ? false : true;
			input[i] = input[i] ? false : true;
			input[i + 1] = input[i + 1] ? false : true;
			mini++;
		}
	}
	if (input[n - 2] == output[n - 2] && input[n - 1] == output[n - 1]) ;
	else if (input[n - 2] != output[n - 2] && input[n - 1] != output[n - 1]) mini += 1;
	else mini = 1000000;

	int mini2 = 0;
	for (int i = 1; i < n - 1; i++) {
		if (input2[i - 1] != output[i - 1]) {
			input2[i - 1] = input2[i - 1] ? false : true;
			input2[i] = input2[i] ? false : true;
			input2[i + 1] = input2[i + 1] ? false : true;
			mini2++;
		}
	}
	if (input2[n - 2] == output[n - 2] && input2[n - 1] == output[n - 1]);
	else if (input2[n - 2] != output[n - 2] && input2[n - 1] != output[n - 1]) mini2 += 1;
	else mini2 = 1000000;

	if (mini == 1000000 && mini2 == 1000000) cout << -1;
	else cout << min(mini, mini2);
}

재채점 중이라 맞았습니다가 회색인 것 같다.

1. 문자열 굳이 숫자로 바꿔주기

2. 함수? 그게 뭔데

3. 인덱스 범위? 따로 빼

4. 입력 배열 두 개 사용하기

힘들게 산다...

놀라운 건 위 아래 코드의 차이점이 메모리 쬐끔...?이다.

물론 가독성이 제일 차이난다.