[G4] 백준 2138번 전구와 스위치 C++ 그리디 알고리즘

리뷰

 

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

스위치를 누르면 현재 위치와 양쪽 방향의 전구가 모두 반전된다.

스위치를 적절히 눌러 시작 전구의 상태에서 목표 전구의 상태까지 도달하고, 그 최소 횟수를 출력하는 문제

 

 

전역 변수

• n : 주어지는 전구의 개수
• ans1, ans2 : 케이스를 1, 2로 나누어 스위치를 누른 횟수를 저장할 변수

 

함수

1. toggle

void toggle(string& f, int idx)

 

스위치를 클릭할 경우 전구의 켜짐과 꺼짐을 관리할 함수

1. 매개변수로 변경할 문자열의 포인터 f, 변경할 인덱스 idx를 받는다.
2. 만약 idx가 n - 1일 경우 문자열의 끝이므로 idx -1, idx의 전구를 반전시킨다.
3. 아닐 경우 idx -1, idx, idx + 1의 전구를 반전시킨다.

 

문제풀이

1. 문자열 f1, f2, e를 초기화 한다, f1은 초기 문자열 f2는 첫번째 스위치를 누른 문자열, e는 목표 문자열이다.
2. n, f1, e를 입력 받고, 만약 f1과 e가 동일하다면 탐색할 필요가 없으므로 0을 출력하고 main함수를 종료한다.
3. 초기 f2의 값은 f1을 그대로 복사하여 저장해 준다.
4. 만약 f2[0], f2[1]이 '1'이라면 '0'를 '0'이라면 '1'로 변경하고 ans2를 증가시킨다.
5. 1 ~ n - 1까지 탐색을 하며 f1, f2의 i - 1인덱스가 e의 i - 1인덱스와 다르다면 toggle함수를 실행한다.
6. toggle함수를 실행할땐 각각의 문자열과 현재 인덱스를 매개변수로 전달하고 ans값을 증가시킨다.
7. 스위치를 누르는 작업를 마치고 f1, f2가 모두 e와 같다면 ans1, ans2중 더 작은값을 출력한다.
8. f1이 e와 같다면 ans1을, f2가 e와 같다면 ans2를, 둘다 e와 다르다면 -1을 출력해 준다.

 

참고 사항

• 초기 스위치를 누르냐 누르지않냐로 케이스가 나뉘어 진다.
• f1은 초기 스위치를 누르지 않은 문자열, f2는 초기 스위치를 누른 문자열이다.
• 현재 인덱스의 이전 인덱스가 e와 다른지만 체크해주면서 스위치를 눌러주면 된다.

 

정답 코드

#include<iostream>
#include<algorithm>
using namespace std;

int n, ans1, ans2;

void toggle(string& f, int idx) {
	if (idx == n - 1) {
		f[idx - 1] = f[idx - 1] == '1' ? '0' : '1';
		f[idx] = f[idx] == '1' ? '0' : '1';
	}
	else {
		f[idx - 1] = f[idx - 1] == '1' ? '0' : '1';
		f[idx] = f[idx] == '1' ? '0' : '1';
		f[idx + 1] = f[idx + 1] == '1' ? '0' : '1';
	}
}

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

	string f1, f2, e;
	cin >> n >> f1 >> e;
	if (f1 == e) {
		cout << 0;
		return 0;
	}

	f2 = f1;
	f2[0] = f2[0] == '1' ? '0' : '1';
	f2[1] = f2[1] == '1' ? '0' : '1';
	ans2++;
	for (int i = 1; i < n; i++) {
		if (f1[i - 1] != e[i - 1]) {
			toggle(f1, i);
			ans1++;
		}
		if (f2[i - 1] != e[i - 1]) {
			toggle(f2, i);
			ans2++;
		}
	}

	if (f1 == e && f2 == e) cout << min(ans1, ans2);
	else if (f1 == e) cout << ans1;
	else if (f2 == e) cout << ans2;
	else cout << -1;
}