BOJ_2138 전구와 스위치 Gold.5

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

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

제한 사항
N(2 <= N <= 100,000) 주어진다.

이 문제에 대해 Brute Force를 진행한다고 하면 시간 복잡도를 고려했을 때, 시간 초과가 난다.

그렇다면 어떻게 문제를 해결해야할지, 딱히 알고리즘이 생각나지 않는다면 Greedy하게 접근해봐야 한다.

현재 상황에서의 최적의 해 -> 부분 최적 해를 만들어 나가는 것이 핵심이다.

바로 직전 인덱스가 가리키는 배열의 요소가 같지 않다면 현재 인덱스의 전구를 바꿔주면 같은 것으로 바꿔줄 수 있는 것이다.
반대로, 바로 직전 인덱스가 가리키는 배열의 요소가 같다면 현재 인덱스의 전구를 바꿔 줄 필요가 없기 때문에 현재 인덱스까지 만들고자 하는 스위치의 부분 최적해를 만족할 수 있는 것이다.

단 주의할 점으로 첫번째 전구의 상태를 바꾼 것과 바꾸지 않은 것을 고려하여 코드를 작성하면 된다

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

public class Main {
    private static int N;
    private static int[] original;
    private static int[] target;
    private static int answer = Integer.MAX_VALUE;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 2 <= N <= 100,000
        N = Integer.parseInt(br.readLine());

        original = Arrays.stream(br.readLine().split("")).mapToInt(Integer::parseInt).toArray();
        target = Arrays.stream(br.readLine().split("")).mapToInt(Integer::parseInt).toArray();

        answer = Math.min(answer, change(original, 0));

        original[0] = 1 - original[0];
        original[1] = 1 - original[1];

        answer = Math.min(answer, change(original, 1));

        if(answer == Integer.MAX_VALUE) System.out.println(-1);
        else System.out.println(answer);
    }

    private static int change(int[] A, int count) {
        A = A.clone();

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

            for (int j = i - 1; j < i + 2; j++) {
                if (j < N) {
                    A[j] = 1 - A[j];
                }
            }
            count++;
        }

        for (int i = 0; i < N; i++) {
            if(A[i] != target[i]) return Integer.MAX_VALUE;
        }
        return count;
    }
}