BOJ 2138 전구와 스위치

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

문제

N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 있는 전구는 켜지고, 켜져 있는 전구는 꺼지게 된다. 1번 스위치를 눌렀을 경우에는 1, 2번 전구의 상태가 바뀌고, N번 스위치를 눌렀을 경우에는 N-1, N번 전구의 상태가 바뀐다.

N개의 전구들의 현재 상태와 우리가 만들고자 하는 상태가 주어졌을 때, 그 상태를 만들기 위해 스위치를 최소 몇 번 누르면 되는지 알아내는 프로그램을 작성하시오.

---

입력

첫째 줄에 자연수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 전구들의 현재 상태를 나타내는 숫자 N개가 공백 없이 주어진다. 그 다음 줄에는 우리가 만들고자 하는 전구들의 상태를 나타내는 숫자 N개가 공백 없이 주어진다. 0은 켜져 있는 상태, 1은 꺼져 있는 상태를 의미한다.

---

출력

첫째 줄에 답을 출력한다. 불가능한 경우에는 -1을 출력한다.

---

예제 입력 1

3
000
010

예제 출력 1

3

---

코드

100,000개의 스위치가 있기 때문에, 브루트포스로 풀 수는 없다.

또한, 스위치를 누를 때 3개의 전구 상태를 변화시키기 때문에, 스위치와 전구를 여러 개의 작은 범위로 분할해서 DP로 풀 수는 없을 것 같다.

그래서 문제에 대해 조금 더 생각해봤다.

1번 전구에 영향을 줄 수 있는 스위치는 1번, 2번 스위치밖에 없다.

만약 1번 스위치를 누른 상태일 때, 만들고자 하는 전구의 상태로 만들기 위해서는 3번 ~ N번 스위치는 1번 전구에 어떠한 영향도 끼칠 수 없기 때문에, 2번 스위치를 누를지 말지는 자동으로 결정된다.

예를 들어, 1번 스위치를 누른 상태가 011...이라고 해보자.

목표로 하는 상태가 101...일 경우, 2번 스위치는 자동으로 눌러야만 한다.

마찬가지로, 그 이후의 상황에 따라 3번, 4번등 각 스위치를 목표로 하는 상태가 되기 위해 누를지 말지 자동으로 결정되게 돼있다.

그렇게 마지막까지 전구 상태를 변화시키고, 마지막 전구의 상태가 목표하는 마지막 전구의 상태와 같다면, 목표하는 상태로 변화시킬 수 있다는 것이다.

즉, 우리는 1번 스위치를 누른 상태와 누르지 않은 상태 두 가지를 검사하면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int answer = 0;
        boolean[] current = new boolean[N];
        boolean[] target = new boolean[N];

        String currentInput = br.readLine();
        String targetInput = br.readLine();

        // 처음 입력받은 상태가 목표하는 상태와 동일할 경우
        if(currentInput.equals(targetInput)) {
            System.out.println(answer);
            return;
        }

        for (int i = 0; i < N; i++) {
            if(currentInput.charAt(i) == '1') {
                current[i] = true;
            }

            if(targetInput.charAt(i) == '1') {
                target[i] = true;
            }
        }

        boolean[] firstPushed = current.clone();
        firstPushed[0] = !firstPushed[0];
        firstPushed[1] = !firstPushed[1];

        int firstPushedCount = countNumberOfPush(firstPushed, target, 1);
        int firstNonPushedCount = countNumberOfPush(current, target, 0);

        if(firstPushedCount == -1) {
            answer = firstNonPushedCount;
        } else if(firstNonPushedCount == -1) {
            answer = firstPushedCount;
        } else {
            answer = Integer.min(firstPushedCount, firstNonPushedCount);
        }

        System.out.println(answer);
    }

    static int countNumberOfPush(boolean[] current, boolean[] target, int numberOfPush) {
        int searchBoundary = current.length - 2; 
        
        for (int i = 0; i < searchBoundary; i++) {
            if(current[i] != target[i]) {
                numberOfPush++;
                for (int j = i; j <= i + 2; j++) {
                    current[j] = !current[j];
                }
            }
        }

        if(current[searchBoundary] != target[searchBoundary]) {
            numberOfPush++;
            current[searchBoundary] = !current[searchBoundary];
            current[searchBoundary + 1] = !current[searchBoundary + 1];
        }

        if(current[searchBoundary + 1] != target[searchBoundary + 1]) {
            return -1;
        }

        return numberOfPush;
    }
}