[백준] 2138번 : 전구와 스위치 - JAVA [자바]

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

그리디 알고리즘 문제이다.

i 번째에서 현재 전구의 상태와 목표하는 전구의 상태를 보고 i 번째 스위치를 킬지 말지 정하면 안된다.

예제를 잘보면 N 번째 스위치로 N-1 번째 전구의 최종 상태를 결정한다는 것을 볼 수 있다. 왼쪽에서부터 탐색하므로 N 번째 스위치는 N-1, N, N+1 번째 전구의 상태를 결정하고 그 뒤 N+1 번째 스위치는 N, N+1, N+2 번째 전구의 상태를 결정한다. N+1번째 스위치로 넘어온 순간 그 전에 변경됐던 N, N+1 번째 전구의 상태는 변경할 수 있는 반면 N-1 번째 전구의 상태는 변경할 수 없다.

즉, 전구 배열을 탐색하면서 현재 스위치의 전 순서의 전구 상태를 보고 스위치를 킬지 말지 정하면 된다.

하지만 여기서 문제가 있다. 1 번째 스위치는 0번째 전구의 상태를 봐야 하는데, 0번째 전구는 존재 하지 않는다. 그러므로 두 가지의 상황을 가정하여 문제를 풀어야 한다.

1. 첫번째 스위치를 안킬 경우
   • 이 경우 아무 조작을 하지 않고 진행하면 된다.
   • 하지만, 원래의 배열을 바꾸는 행위가 있으므로 클론한 배열을 사용한다.(다음 상황에 영향을 주기 때문에)
2. 첫번째 스위치를 킬 경우
   • 배열의 1, 2 번째 전구의 상태를 바꾸며 스위치를 킨 횟수도 1부터 시작하여 탐색한다.

두 가지의 상황에서 알고리즘을 수행하여 정답을 도출하면 된다.

public class bj2138 {

    static int N, answer = Integer.MAX_VALUE;
    static int[] goal;

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

        N = Integer.parseInt(br.readLine());

        int[] current = new int[N];
        goal = new int[N];

        char[] charArray = br.readLine().toCharArray();
        for (int i = 0; i < N; i++) {
            current[i] = charArray[i] - '0';
        }

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

        // i 번째 스위치를 사용해서 i-1 번째 전구의 최종 상태를 결정한다.
        // 1 번째 스위치를 킬지 말지는 그 전의 전구가 없으므로 고를 수 없다.
        // 1 번째 스위치를 킬지 말지 두 가지 상황에 대해 알고리즘을 적용한다.

        // 1 번째 스위치를 안킨다 (그냥 진행)
        int[] tmp;
        tmp = current.clone();
        int count = 0;
        greedy(1, count, tmp);

        // 1 번째 스위치를 킨다
        current[0] = (current[0] == 0 ? 1 : 0);
        current[1] = (current[1] == 0 ? 1 : 0);
        count = 1;
        greedy(1, count, current);

        System.out.println(answer == Integer.MAX_VALUE ? -1 : answer);

        br.close();
    }

    public static void greedy(int index, int count, int[] arr) {
        if (index == N) {
            if (arr[index - 1] == goal[index - 1]) {
                answer = Math.min(answer, count);
            }
            return;
        }

        // index-1 번째 전구의 상태가 다르면
        // index 번째 스위치를 눌러서 바꿔야 한다.
        if (arr[index - 1] != goal[index - 1]) {
            // index 번째 스위치 사용
            for (int i = index - 1; i <= index + 1; i++) {
                if (i >= N || i < 0) continue;
                arr[i] = (arr[i] == 0) ? 1 : 0;
            }
            greedy(index + 1, count + 1, arr);
        } else greedy(index + 1, count, arr);
    }
}