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

 

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

 

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

 

 

---

 

 

해결전략

 

그리디 알고리즘 Greedy Algorithm

 

---

 

 

정답코드

 

#include <iostream> 
#include <vector> 
#include <string> 
using namespace std; 

int n; 			// 스위치의 개수를 저장할 변수
string initial; // 초기 문자열
string target;  // 목표 문자열

void ToggleSwitch(int k, string& v) // 스위치를 조작하는 함수, k번째 스위치를 누르면 k-1, k, k+1의 상태가 변경됨
{
	if (0 <= k - 1)
		v[k - 1] = v[k - 1] == '0' ? '1' : '0';

	if (0 <= k && k < n)
		v[k] = v[k] == '0' ? '1' : '0';

	if (k + 1 < n)
		v[k + 1] = v[k + 1] == '0' ? '1' : '0';
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); // 입출력 속도 향상을 위한 설정

	cin >> n; 
	cin >> initial;	       // 초기 문자열 입력
	cin >> target;  	   // 목표 문자열 입력
	string tmp1 = initial; // 첫번째 시나리오를 위한 임시 문자열
	string tmp2 = initial; // 두번째 시나리오를 위한 임시 문자열

	// 첫 번째 스위치를 누르는 경우의 시나리오
	ToggleSwitch(0, tmp1); // 첫번째 스위치 누름
	int cnt1 = 1; // 스위치 누른 횟수 카운트 (이미 1번 누름)
	for (int i = 0; i < n; i++) // 두 번째 스위치부터 마지막 스위치까지 반복
	{
    	// 현재 상태가 목표와 다를 경우
		if (tmp1[i] != target[i]) 
		{
			if (i == n - 1) { // 마지막 스위치인데 목표와 다를 경우 실패
				cnt1 = -1;
				break;
			}
			ToggleSwitch(i + 1, tmp1); // 다음 스위치 누름
			cnt1++;
		}
        
        // 더 이상 확인하지 않을 이전 위치가 다른 경우가 다른 경우
        if (0 <= i - 1 && tmp1[i - 1] != target[i - 1]) {
			cnt1 = -1;
			break;
		}
	}

	// 첫 번째 스위치를 누르지 않는 경우의 시나리오
	int cnt2 = 0; // 스위치 누른 횟수 카운트
	for (int i = 0; i < n; i++) // 첫 번째 스위치부터 마지막 스위치까지 반복
	{
    	// 현재 상태가 목표와 다를 경우
		if (tmp2[i] != target[i]) 
		{
			if (i == n - 1) { // 마지막 스위치인데 목표와 다를 경우 실패
				cnt2 = -1;
				break;
			}
			ToggleSwitch(i + 1, tmp2); // 다음 스위치 누름
			cnt2++;
		}
        
         // 더 이상 확인하지 않을 이전 위치가 다른 경우가 다른 경우
        if (0 <= i - 1 && tmp2[i - 1] != target[i - 1]) {
			cnt2 = -1;
			break;
		}
	}

	int answer; // 최종 답안
	// 두 시나리오 모두 실패, 하나만 성공, 둘 다 성공한 경우를 나누어 처리
	if (cnt1 == -1 && cnt2 == -1) answer = -1;
	else if (cnt1 == -1 && cnt2 != -1) answer = cnt2;
	else if (cnt1 != -1 && cnt2 == -1) answer = cnt1;
	else answer = min(cnt1, cnt2); // 둘 다 성공한 경우 더 적은 횟수 선택

	cout << answer; // 최종 답안 출력

	return 0; // 프로그램 종료
}

 

 

---

 

정답코드룰 간략화한 버젼

 

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int n;
string initial, target;

void toggleSwitch(string& v, int k) {
    for (int i = k - 1; i <= k + 1; i++) {
        if (i >= 0 && i < n) {
            v[i] = v[i] == '0' ? '1' : '0';
        }
    }
}

int solve(string v, bool pressFirst) 
{
    int cnt = 0;
    if (pressFirst) {
        toggleSwitch(v, 0);
        cnt++;
    }
    for (int i = 1; i < n; i++) {
        if (v[i - 1] != target[i - 1]) {
            toggleSwitch(v, i);
            cnt++;
        }
    }
    
    if (v != target) return -1;
    return cnt;
}

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

    cin >> n >> initial >> target;

    int cnt1 = solve(initial, true); // 첫 번째 스위치를 누른 경우
    int cnt2 = solve(initial, false); // 첫 번째 스위치를 누르지 않은 경우

    if (cnt1 == -1 && cnt2 == -1) cout << -1;
    else if (cnt1 == -1) cout << cnt2;
    else if (cnt2 == -1) cout << cnt1;
    else cout << min(cnt1, cnt2);

    return 0;
}

 

 

---