[백준, C++] 2138 - 전구와 스위치

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

2138번: 전구와 스위치

 

문제 분석

N개의 전구와 N개의 스위치가 있다. i번 스위치를 누르면, i - 1, i, i + 1번째 전구의 상태가 토글된다(ON -> OFF, OFF -> ON). 현재 전구의 상태와 만들고자 하는 전구의 상태가 주어질 때, 만들고자 하는 전구의 상태로 변화시키기 위해 최소한 몇 번의 스위치를 눌러야 하는지를 구하는 문제이다.

문제를 처음 접했을 때 되게 막막하다고 생각했다. 문제를 최대한 단순하게 생각해보려고 노력했다. 너무나 당연한 말일 수 있지만, 이 두 가지가 내 눈에 보였다.

 

1. 같은 스위치를 2번 누를 필요는 없다. 한 번 누르거나, 아니면 아예 안 누르거나 둘 중 하나만 하면 된다.

2. 스위치를 누르는 순서는 중요하지 않다.

3. 앞 스위치(i번 스위치)부터 순차적으로 누르거나 안 누르는 행위를 하면, 그 다음 스위치(i + 1번 스위치)만이 유일하게 직전 전구(i번 전구)의 상태를 변경시킬 수 있게 된다.

 

일단 1번을 먼저 보자. 같은 스위치를 2번 누르는 행위는 상태를 원복시키는 행위이다. 3번 누르는 행위는 결국 1번 누르는 행위와 같다. 따라서 굳이 한 스위치를 2번 이상 누를 필요가 없는 것이다.

 

다음으로 2번을 보자. 내가 i번 스위치를 누른 후 i + 1번 스위치를 누르나, i + 1번 스위치를 누른 후 i번 스위치를 누르나 그 결과는 같다. 예시로 초기 전구 상태가 000이고, 1번 스위치와 2번 스위치를 가지고 생각해보자.

1번 스위치를 먼저 누르면 000에서 111이 된다. 그리고 직후 2번 스위치를 누르면 111에서 100이 된다.

2번 스위치를 먼저 누르면 000에서 011이 된다. 그리고 직후 1번 스위치를 누르면 011에서 100이 된다.

 

마지막으로 3번을 보자. 우리는 1번과 2번을 통해 한 스위치를 굳이 2번 이상 누를 필요가 없음을 알았고, 스위치를 누르는 순서 역시 중요하지 않음을 알게 되었다. 그렇다면 스위치를 누른다 / 만다 라는 2가지 선택권이 있고, 그 선택을 앞 전구부터 순차적으로 진행해도 결과에는 영향이 없다는 근거를 얻게 된 것이다. 사실 문제 해결을 위한 핵심은 3번이다. 1번과 2번은 3번이 말이 된다는 것을 뒷받침해주는 근거에 불과하다.

 

위의 예시처럼 초기 전구 상태가 000이고, 우리가 만들고자 하는 전구의 상태는 010이라고 해보자. 우리는 0번 전구에 대해 스위치를 누른다 / 만다 라는 2가지 선택을 할 수 있다. 따라서 우리는 이 2개의 케이스를 분리해 생각하는 것으로 출발할 것이다.

 

1) 0번 스위치를 누르는 경우

0번 스위치를 누른 후 전구의 상태 : 110

우리는 이미 0번 스위치를 눌렀으므로 0번 스위치를 한 번 더 누를 이유는 굳이 없다. 그렇다면 다음 스위치인 1번 스위치를 보자. 1번 스위치를 눌러야 할까 ? 정답은 눌러야 한다이다. 그 이유는, 우리가 이미 0번 스위치를 지나왔기 때문에 0번 전구의 상태를 변경시킬 수 있는 유일한 수단은 1번 스위치이기 때문이다.

0번 스위치를 누른 후 전구의 상태 : 110

1번 스위치를 누른 후 전구의 상태 : 001

그럼 이제 2번 스위치를 눌러야 하는지에 대해 생각해보자. 1번 전구는 현재 0이다. 하지만 우리는 1번 전구를 1이라는 상태로 만들어야 한다. 따라서 2번 스위치를 반드시 눌러야만 한다.

0번 스위치를 누른 후 전구의 상태 : 110

1번 스위치를 누른 후 전구의 상태 : 001

2번 스위치를 누른 후 전구의 상태 : 010

운이 좋게도 우리는 만들고자 하는 전구의 상태로 전구를 변화시키는 데 성공했다. 3회만에 말이다. 그런데, 마지막 스위치까지 눌렀는데도 전구를 원하는 상태로 만들지 못하는 경우는 어떻게 해야 할까 ? 이번에는 0번 스위치를 누르지 않는 경우를 생각해보자.

 

2) 0번 스위치를 누르지 않는 경우

0번 스위치를 누르지 않은 후 전구의 상태 : 000

다음 스위치인 1번 스위치를 보자. 우리가 만들어야 하는 전구의 상태는 010이다. 그런데 1번 스위치를 누르게 되면 0번 전구의 상태를 토글시킬 유일한 스위치를 눌러버리는 꼴이 된다. 따라서 1번 스위치를 누르면 안 된다.

0번 스위치를 누르지 않은 후 전구의 상태 : 000

1번 스위치를 누르지 않은 후 전구의 상태 : 000

2번 스위치를 보자. 우리는 1번 전구를 0이 아닌 1로 만들어야 한다. 그리고 이 2번 스위치가 1번 전구를 변화시킬 수 있는 유일한 수단이다. 따라서 2번 스위치는 눌러야 한다.

0번 스위치를 누르지 않은 후 전구의 상태 : 000

1번 스위치를 누르지 않은 후 전구의 상태 : 000

2번 스위치를 누른 후 전구의 상태 : 011

아뿔싸 ~ 만들고자 하는 전구의 상태로 변환하는 데 실패했다. 즉, 0번 스위치를 누르지 않고 시작하면 우리는 원하는 결과를 얻을 수 없는 것이다.

 

즉, 이 문제를 푸는 방법은 i번 스위치가 i - 1번 전구의 상태를 변화시킬 유일한 수단이다는 점에만 초점을 맞춰 진행하는 것이다. 그렇게 마지막 스위치까지 체크했을 때, 스위치들을 다 누른 결과가 우리가 만들고자하는 전구의 상태라면 우리는 스위치를 누른 횟수를 출력값으로 갱신하면 된다.

 

코드

#include <iostream>
#include <cstring>
#define MAX 100001

using namespace std;

int n;
string input;
string output;
int result = MAX;

void getInput();
void solve();
void printResult();

char toggle(char c);
string toggle(string str, int index);

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

    getInput();
    solve();
    printResult();

    return 0;
}

void getInput() {
    cin >> n;
    cin >> input;
    cin >> output;
}

char toggle(char c) {
    if (c == '0') {
        return '1';
    }
    return '0';
}

string toggle(string str, int index)  {
    if (index == 0) {
        str[index] = toggle(str[index]);
        str[index + 1] = toggle(str[index + 1]);
    } else if (index == str.length() - 1) {
        str[index - 1] = toggle(str[index - 1]);
        str[index] = toggle(str[index]);
    } else {
        str[index - 1] = toggle(str[index - 1]);
        str[index] = toggle(str[index]);
        str[index + 1] = toggle(str[index + 1]);
    }

    return str;
}

void solve() {
    // 1. 0번 스위치를 누른 경우
    string str1 = input;
    int count1 = 0;

    str1 = toggle(str1, 0);
    count1++;
    
    for (int i = 1; i < str1.length(); i++) {
        if (str1[i - 1] != output[i - 1]) {
            str1 = toggle(str1, i);
            count1++;
        }
    }

    if (str1 == output) {
        result = min(result, count1);
    }

    // 2. 0번 스위치를 누르지 않은 경우
    string str2 = input;
    int count2 = 0;

    for (int i = 1; i < str2.length(); i++) {
        if (str2[i - 1] != output[i - 1]) {
            str2 = toggle(str2, i);
            count2++;
        }
    }

    if (str2 == output) {
        result = min(result, count2);
    }

    if (result == MAX) {
        result = -1;
    }
}

void printResult() {
    cout << result << "\n";
}

 

코드 설명

앞에서 설명한 바와 같이 문제 풀이는 2단계로 나눴다. 0번 스위치를 누른 경우 / 0번 스위치를 누르지 않는 경우로 나눠서 말이다.

 

이 과정에서 문자를 토글시킨 값을 반환하는 char toggle(char c)라는 메서드와, char toggle(char)을 활용해 특정 인덱스의 스위치를 누를 때 관련된 문자들을 토글시킨 문자열을 반환하는 string toggle(string str, int index)라는 메서드를 만들었다.

 

또, 스위치를 순차 탐색할 때 앞서 설명한 바와 같이 i번 스위치가 i - 1번 전구의 상태를 변경시킬 유일한 스위치라는 것을 활용해 반복문을 작성했다.

 

다 풀고나면 골드 치고 쉽다는 생각이 들지만, 이 풀이를 생각하는 과정을 고려했을 때는 이 문제가 골드값은 하는 것 같다고 생각이 든다.