[BOJ] 2138. 전구와 스위치 - Java

2138.전구와 스위치: https://www.acmicpc.net/problem/2138

문제 설명

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

문제 접근

그리디에 취약하기에 결국 문제를 풀지 못하였다. 어떤 분의 접근방법을 참고하였다.

befer: 0000 after: 0101이 있을경우 before에서 after로 스위치 상태를 바꿀 수 있는가?

1. i번 스위치를 누를 때 i번 스위치만 바뀔경우
직관적으로 before과 after을 비교하면서 i번째의 전구 상태가 다를경우 해당 전구를 켜주면 된다. 왜냐하면 그 때 켜지 않으면 앞으로 그 전구 상태를 바꿀 수 없다. i + 1번째로 넘어가게 되면 영영 i번째 전구를 어찌할 방도가 없다!
따라서 2번 전구와 4번 전구를 켜주는게 최소 횟수로 켤 수 있다. (2번)

2. i번 스위치를 누를 때 i번, i+1번 스위치가 바뀔경우
위와 비슷하다. 1번 스위치를 누르면 1번, 2번의 상태가 바뀐다. 마찬가지로 2번 스위치를 누르면 2번, 3번의 상태가 바뀐다. 2번 전구는 1번 스위치, 또는 2번 스위치를 통해 상태가 바뀔 수 있다. 그럼 1번 전구는 결국 1번에서 누르지 않는다면 상태가 바뀌지 않아 어찌할 방도가 없다!

3. 그럼 문제의 i번 스위치를 누를때 i-1번, i번, i+1번 스위치가 바뀔경우엔?
간단하다. before과 after의 i-1번 전구 상태가 다르다면 i-1번 전구상태를 바꾸는 i번 스위치를 누르면 된다.
다음에서 1번 전구의 상태가 다르다. 따라서 2번전구의 스위치를 눌러서 1번 전구의 상태를 바꿔주면 된다. 2번 전구는 3번전구의 스위치를 눌러서 바꿔주면 된다. 이렇게 순차적으로 선형탐색 O(N)을 해주면 된다.

이렇게 하면 근데 틀린다. (이왜틀?)

0번 전구를 가정했을 때 0번 전구의 상태를 모른다. 0번 전구의 before과 after이 같을 수도 있고, 다를 수도 있다.
만약 같다면, 1번 스위치를 누를 필요가 없어 0, 1, 2번 전구 상태는 그대로다.
만약 다르다면, 1번 스위치를 눌러야하고, 이로 인해 0, 1, 2번 전구 상태가 바뀐다.
따라서 두 개의 경우를 나누어서 생각해야한다.
(문제를 푸는데 0번 스위치까지 생각해야해? 라고 할 수 있지만, 이 문제는 양 끝 스위치는 2개의 상태만 변경된다고 가정을 했다. 결국 0번 전구도 상태가 바뀐다는 말이지만, 배열의 범위 내에서 개연성있게 위와 같은 말로 치환했다고 생각했다.)

int a = solve(before, after); // 1번 스위치 누르지 않음
int[] copy = Arrays.copyOf(before, before.length);
copy[0] = 1 - copy[0];
copy[1] = 1 - copy[1];
int b = solve(copy, after); // 1번 스위치 누름

그럼 마지막 N번 전구상태도 따로 해주어야할게 있는가?

마지막 N번 전구는 N-1번 전구, N번 전구의 상태만 교체한다.

for(int i = 1; i < b.length; i++) {
	if(b[i - 1] != a[i - 1]) { 
		b[i - 1] = 1 - b[i - 1]; // n - 1번 전구
		b[i] = 1 - b[i]; // n 번 전구
	if(i != b.length - 1) { // 인덱스가 N이 아닐경우
		b[i + 1] = 1 - b[i + 1]; // n + 1번 전구
	}
	cnt++;
	}
}

전체 코드

package enterprise.sw_category;

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

public class BOJ2138 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] _before = br.readLine().split("");
        String[] _after = br.readLine().split("");
        int[] before = changeToIntArray(_before);
        int[] after = changeToIntArray(_after);
        if(isSame(before, after)) System.out.println(0);
        else {
//            System.out.println(Arrays.toString(copy));
            int a = solve(before, after); // 첫번째 바꿈 X
            int[] copy = Arrays.copyOf(before, before.length);
            copy[0] = 1 - copy[0];
            copy[1] = 1 - copy[1];
            int b = solve(copy, after); // 첫번째 바꿈 
            if(a == (int)1e9 && b == (int)1e9) System.out.println(-1);
            System.out.println(Math.min(a, b + 1));

        }
    }

    static int solve(int[] b, int[] a) {
        int cnt = 0;
        for(int i = 1; i < b.length; i++) {
            if(b[i - 1] != a[i - 1]) {
                b[i - 1] = 1 - b[i - 1];
                b[i] = 1 - b[i];
                if(i != b.length - 1) {
                    b[i + 1] = 1 - b[i + 1];
                }
                cnt++;
            }
        }
        if(isSame(a, b)) return cnt;
        return (int)1e9;
    }

    static int[] changeToIntArray(String[] s) {
        int[] tmp = new int[s.length];
        for(int i = 0; i < s.length; i++) {
            tmp[i] = Integer.parseInt(s[i]);
        }
        return tmp;
    }

    static boolean isSame(int[] a ,int[] b) {
        boolean flag = true;
        for(int i = 0; i < a.length; i++) {
            if(a[i] == b[i]) continue;
            if(a[i] != b[i]) return false;
        }
        return flag;
    }
}