[백준]2138: 전구와 스위치(java)

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

2138번: 전구와 스위치

문제

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

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

입력

첫째 줄에 자연수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 전구들의 현재 상태를 나타내는 숫자 N개가 공백 없이 주어진다. 그 다음 줄에는 우리가 만들고자 하는 전구들의 상태를 나타내는 숫자 N개가 공백 없이 주어진다. 0은 켜져 있는 상태, 1은 꺼져 있는 상태를 의미한다.

출력

첫째 줄에 답을 출력한다. 불가능한 경우에는 -1을 출력한다.

예제 입력 1 

3
000
010

예제 출력 1 

3

---

풀이

X이라는 자리의 전구 스위치를 누른다면 X-1, X, X+1의 전구 상태가 변하게 된다.

X을 기준으로 생각했을 때 양 옆의 상태를 모두 생각해야하는 매우 복잡한 상황에 놓이게된다.

어떻게하면 조금 더 단순하게 생각할 수 있을까?란 고민끝에 직전기준으로 비교하자. 라는 견론이 나왔다.

이유는 다음과 같다.

X-1의 상태만으로 전구를 키고 끈다면 X는 X+1에서 X+1은 X+2에서 다시 확인하고 변경되기때문이다.

이렇게 쭉 모든 상태를 바꾸고나면 끝자리인 N은 확인해줄 N+1이 없기때문에 N의 상태가 동일하면 정답이 될 수 있게된다.

한가지 더 예외가 존재한다.

0번째를 키는 경우이다.

우리는 X를 킬 때 X+1에서 키는 로직을 구현하기로했는데 그렇다면 0번째 스위치는 누르는 경우가 없다.

하지만 0번째 스위치를 누르는게 최소가 될 수 있기 때문에 0번재 스위치를 누른경우와 누르지 않은경우 두가지의 결과를 구해서 최솟값을 비교해주면 된다.

 

전체 코드

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

public class BJ_S1_2138_전구와스위치 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringBuilder arr1 = new StringBuilder(br.readLine());
        StringBuilder arr2 = new StringBuilder(arr1);
        StringBuilder ans = new StringBuilder(br.readLine());

        int pushCnt1 = 1;
        int pushCnt2 = 0;
        arr1.setCharAt(0,  arr1.charAt(0) == '1' ? '0' : '1');
        arr1.setCharAt(1,  arr1.charAt(1) == '1' ? '0' : '1');

        for(int i=1; i<N; i++) {
            if(arr1.charAt(i-1) != ans.charAt(i-1)) {
                if(i==N-1) {
                    arr1.setCharAt(i-1,  arr1.charAt(i-1) == '1' ? '0' : '1');
                    arr1.setCharAt(i,  arr1.charAt(i) == '1' ? '0' : '1');
                } else {
                    arr1.setCharAt(i-1,  arr1.charAt(i-1) == '1' ? '0' : '1');
                    arr1.setCharAt(i,  arr1.charAt(i) == '1' ? '0' : '1');
                    arr1.setCharAt(i+1,  arr1.charAt(i+1) == '1' ? '0' : '1');
                }
                pushCnt1++;
            }
            if(arr2.charAt(i-1) != ans.charAt(i-1)) {
                if(i==N-1) {
                    arr2.setCharAt(i-1,  arr2.charAt(i-1) == '1' ? '0' : '1');
                    arr2.setCharAt(i,  arr2.charAt(i) == '1' ? '0' : '1');
                } else {
                    arr2.setCharAt(i-1,  arr2.charAt(i-1) == '1' ? '0' : '1');
                    arr2.setCharAt(i,  arr2.charAt(i) == '1' ? '0' : '1');
                    arr2.setCharAt(i+1,  arr2.charAt(i+1) == '1' ? '0' : '1');
                }
                pushCnt2++;
            }
        }
        if(!arr1.toString().equals(ans.toString())) pushCnt1 = Integer.MAX_VALUE;
        if(!arr2.toString().equals(ans.toString())) pushCnt2 = Integer.MAX_VALUE;
        int answer = Math.min(pushCnt1, pushCnt2);
        if(answer == Integer.MAX_VALUE) {
            System.out.printf("-1");
        } else {
            System.out.printf("%d", Math.min(pushCnt1, pushCnt2));
        }
    }
}