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

문제

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

---

문제 요약

N개의 스위치와 N개의 전구가 있다.

 

각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다.

 

i번 스위치를 누르면, i - 1, i, i + 1번에 있는 세 개의 전구 상태가 변화한다.

+ 1번 스위치를 누르면 1, 2번 전구가, N번 스위치를 누르면 N - 1, N번 전구 상태가 변화한다.

(꺼져 있는 전구는 켜지고, 켜져 있는 전구는 꺼진다.)

 

N개의 전구의 현재 상태와 우리가 만들고자 하는 상태가 주어졌을 때, 그 상태를 만들기 위해 스위치를 최소 몇 번 누르면 되는지 출력한다.

---

코드

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

using namespace std;

int n;

int cnt;
int res = 1e9;

string goal;
string start;

int main() {
    cin >> n >> start >> goal;

    // 스위치를 누르지 않아도 똑같은 상태일 경우
    if (start == goal) {
        cout << 0;
        return 0;
    }

    // 1번째 전구의 스위치를 누른 이후, 원하는 상태로 하나씩 변화시키기
    string first_case = start;
    first_case[0] = first_case[0] == '0' ? '1' : '0';
    first_case[1] = first_case[1] == '0' ? '1' : '0';

    // 1번째 전구의 스위치를 누르고 바로 원하는 상태가 된 경우
    if (first_case == goal) {
        cout << 1;
        return 0;
    }

    // 1번째 전구의 스위치를 눌렀으므로 1부터 시작
    cnt = 1;

    // 왼쪽 전구부터 차례로 그리디를 적용하여 변화시키기
    for (int i = 0; i < n - 1; i++) {
        // i번째 전구의 상태가 이미 같으면 건너뛰기
        if (first_case[i] == goal[i]) continue;

        // i + 1번째 스위치 누르기
        first_case[i] = first_case[i] == '0' ? '1' : '0';
        first_case[i + 1] = first_case[i + 1] == '0' ? '1' : '0';
        if (i + 2 < n) {
            first_case[i + 2] = first_case[i + 2] == '0' ? '1' : '0';
        }

        // 변화 수 증가
        cnt++; 

        // 상태가 같아지면, res 갱신
        if (first_case == goal) {
            res = min(res, cnt);
            break;
        }
    }

    // 1번째 전구의 스위치를 누르지 않고, 원하는 상태로 하나씩 변화시키기
    string second_case = start;

    // 1번째 전구의 스위치를 누르지 않았으므로, 1부터 시작
    cnt = 0;

    // 왼쪽 전구부터 차례로 그리디를 적용하여 변화시키기
    for (int i = 0; i < n - 1; i++) {
        // i번째 전구의 상태가 이미 같으면 건너뛰기
        if (second_case[i] == goal[i]) continue;

        // i + 1번째 스위치 누르기
        second_case[i] = second_case[i] == '0' ? '1' : '0';
        second_case[i + 1] = second_case[i + 1] == '0' ? '1' : '0';
        if (i + 2 < n) {
            second_case[i + 2] = second_case[i + 2] == '0' ? '1' : '0';
        }

        // 변화 수 증가
        cnt++;

        // 상태가 같아지면, res 갱신
        if (second_case == goal) {
            res = min(res, cnt);
            break;
        } 
    }

    if (res == 1e9) {
        cout << -1;
        return 0;   
    }

    cout << res;

    return 0;
}

---

코드 설명

그리디 알고리즘을 이용한다.

 

왼쪽 전구부터 차례로, 현재 상태의 i번째 전구와 원하는 상태의 i번째 전구를 비교한다.

 

만약, 두 전구의 상태가 같다면, i + 1번째 전구의 스위치를 누르면 된다.

 

즉, 현재 상태의 i번째 전구를 원하는 상태로 만들기 위해 매 순간 최선의 선택을 하면 된다.

 

이 때, 주의할 점은 첫 번째 전구의 스위치를 누르는 경우와 누르지 않는 경우로 나뉜다는 것이다.