[BOJ 2138] 전구와 스위치

📃 문제

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

 

---

 

💻 코드

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

public class Boj_2138 {
    public static int N;
    public static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    public static int[] init;
    public static int[] firstInit;
    public static int[] target;
    public static int result;
    public static int firstResult;
    public static void main(String[] args) throws Exception {
        N = Integer.parseInt(bf.readLine());
        
        init = new int[N];
        firstInit = new int[N];
        target = new int[N];

        String inputInit = bf.readLine();
        String inputTarget = bf.readLine();
        for(int i = 0; i<N; i++) {
            init[i] = inputInit.charAt(i) - '0';
            firstInit[i] = init[i];
            target[i] = inputTarget.charAt(i) - '0';
        }

        firstInit[0] = 1 - firstInit[0];
        firstInit[1] = 1 - firstInit[1];

        result = 0;
        firstResult = 1;

        for(int i = 1; i<N; i++) {
            if(init[i - 1] != target[i - 1]) {
                init[i - 1] = 1 - init[i - 1];
                init[i] = 1 - init[i];

                if(i != N - 1) {
                    init[i + 1] = 1 - init[i + 1];
                }
                result++;
            }

            if(firstInit[i - 1] != target[i - 1]) {
                firstInit[i - 1] = 1 - firstInit[i - 1];
                firstInit[i] = 1 - firstInit[i];

                if(i != N - 1) {
                    firstInit[i + 1] = 1 - firstInit[i + 1];
                }
                firstResult++;
            }
        }

        for(int i = 0; i<N; i++) {
            if(init[i] != target[i] && result != Integer.MAX_VALUE) {
                result = Integer.MAX_VALUE;
            }

            if(firstInit[i] != target[i] && firstResult != Integer.MAX_VALUE) {
                firstResult = Integer.MAX_VALUE;
            }
        }

        int output = Math.min(result, firstResult);
        if(output == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(output);
        }
    }

}

 

메모리 및 시간

 

---

💡 풀이

단순히 i번의 전구 상태를 비교해서 i번 스위치를 눌러야 할지 말아야 할지 결정하면 안 된다.

i번 스위치를 누르게 되면 i-1, i, i+1의 전구 상태가 바뀌기 때문이다 (= i번 스위치를 누르는 여부에 따라 i-1번의 전구 상태가 달라져서 i-1번에서 목푯과 비교하더라도 그 의미가 없어진다.)

 

따라서 i번 스위치를 눌러야 할지 말아야 할지 결정하기 위해서는 i-1번의 전구 상태를 확인해야 한다.

 

0번 스위치는 i-1번의 전구 상태를 비교할 수 없기 때문에 0번 스위치를 누를 때, 안 누를 때 두 가지로 나뉘어서 비교한다.