백준 2138 JAVA: 전구와 스위치

문제 설명📖

내가 취약하다고 느끼는 알고리즘 유형 중 하나인 Greedy 문제로 주어진 전구 상태에서 전구를 키거나 끄는(0, 1) 작업을 통해 목표하는 상태로 만드는 최소 작업 횟수를 구해야 한다.

풀이 방법✏️

1. 문제 풀이 전 생각해 볼 점

같은 스위치를 두 번 이상 선택하는 건 의미가 없다

전구를 짝수 번 누르는 행위는 아예 누르지 않은 것과 일치하고 홀수 번 누르는 행위는 한 번 누른 것과 일치하기 때문에 전구를 누르는 경우와 누르지 않는 경우 이렇게 두 가지 경우가 전구를 최소한으로 누르게 된다.

특정 칸에 값을 바꾸게 되는 스위치는 몇 번 스위치인지 먼저 생각해야한다.

2번째 전구의 상태를 바꿀 수 있는 스위치는 1번, 2번, 3번 스위치 뿐이다.

2. 풀이 과정

이 문제는 크게 두 가지 과정으로 이루어진다. (1)먼저 스위치를 누르거나 누르지 않는 작업으로 구성된 시뮬레이션을 돌리고, (2)그 후 시뮬레이션에 의해 변경된 전구의 상태가 목표한 전구의 상태(타겟)와 동일한지를 비교한다.

시뮬레이션에서 주목해야할 점은 i번 스위치를 누를지 말지는 i번 전구 이전에 위치한 i-1번 전구 상태에 의해 결정된다는 것이다. 예를들어 2번 스위치는 1번 전구가 목표하는 전구 상태(타겟)와 일치한다면 누르지 않고 일치하지 않다면 누르게 된다. 이와 같은 시뮬레이션을 2번째 스위치부터 마지막 스위치까지 순차적으로 진행한다면 그리디 한 방식을 통해 최적의 해가 구해진다.

하지만 첫 번째 스위치는 이전 스위치가 존재 하지 않는데 어떻게 해야할까??

이를 해결하기 위해 우리는 첫 번째 스위치를 누르는 경우와 누르지 않는 경우 두 가지로 구분하여 시뮬레이션을 진행하고 둘 중 하나의 경우만 목표한 전구의 상태와 동일하다면 그 경우의 작업 횟수를 선택하고 두 경우 모두 타겟값과 일치한다면 그 중 최솟 값을 최적의 해로 결정하게 된다.

소스 코드(feat. 알찬 주석)⌨️

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BJ_2138 {
    static int N;
    static int[] chooseFirst, notChooseFirst, target;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        char[] chars = br.readLine().toCharArray();
        chooseFirst = new int[N];     // 첫 번째 스위치를 누른 경우
        notChooseFirst = new int[N];  // 첫 번째 스위치를 누르지 않은 경우

        for (int i = 0; i < N; i++) {
            chooseFirst[i] = chars[i] - '0';
            notChooseFirst[i] = chars[i] - '0';
        }

        chars = br.readLine().toCharArray();
        target = new int[N];
        for (int i = 0; i < N; i++) {
            target[i] = chars[i] - '0';
        }

        // 첫 번째 스위치를 눌러준다.
        chooseFirst[0] ^= 1;
        chooseFirst[1] ^= 1;

        int chooseFirstCnt = simulation(chooseFirst) + 1; // 첫 번째 스위치를 켰으므로 +1
        int notChooseFirstCnt = simulation(notChooseFirst);

        if (!isSame(chooseFirst) && !isSame(notChooseFirst)) { // 두 경우 모두 target과 다를 경우
            System.out.println(-1);
        }
        if (isSame(chooseFirst) && !isSame(notChooseFirst)) { // 첫 번째 스위치를 킨 경우에만 target과 같을 경우
            System.out.println(chooseFirstCnt);
        }
        if (!isSame(chooseFirst) && isSame(notChooseFirst)) { // 두 번째 스위치를 킨 경우에만 target과 같을 경우
            System.out.println(notChooseFirstCnt);
        }
        if (isSame(chooseFirst) && isSame(notChooseFirst)) { // 두 경우 모두 target과 같을 경우 더 작은 값을 선택
            System.out.println(Math.min(chooseFirstCnt, notChooseFirstCnt));
        }
    }

    private static int simulation(int[] lights) { // 두 번째 스위치 부터 순차적으로 스위치를 켤지 말지 결정
        int ans = 0;
        for (int i = 1; i < N; i++) {
            if (lights[i - 1] != target[i - 1]) {
                lights[i - 1] ^= 1;  // 0 -> 1 or 1 -> 0
                lights[i] ^= 1;
                if (i + 1 < N) {
                    lights[i + 1] ^= 1;
                }
                ans++;
            }
        }
        return ans;
    }

    private static boolean isSame(int[] lights) { // 시뮬레이션이 끝난 후 목표한 상태(target)와 일치하는 지 확인
        for (int i = 0; i < N; i++) {
            if (lights[i] != target[i]) {
                return false;
            }
        }
        return true;
    }
}