백준 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을 출력한다.

풀이

예전에 본 문제와 비슷해서 풀이방법은 쉽게 떠올릴 수 있었다.

먼저, 첫 번째 전구를 킨 경우와 키지 않은 경우로 나눠서 구해주었다.

두 번째부터 N번 째까지 i - 1이 결과값 index와 비교하여 동일하먄 키지 않고 다르면 스위치를 켜서 순차적으로 비교를 해주었다. (마지막 index는 범위를 초과하지 않게 조건문을 추가함)

순차적으로 비교하기 때문에 마지막 index만 결과값이랑 비교해주면 동일한지 알 수 있다.

현재상태와 만들고자 하는 상태가 같으면 스위치를 누른 횟수를 출력하고 다르면 Integer.MAX_VALUE로 값을 설정하고 두 가지 경우에서 둘 다 Integer.MAX_VALUE이면 불가능한 경우이므로 -1을 출력하고 아니라면 스위치를 누른 최소값을 출력해주었다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class boj_2138 {
    static int N;
    static String nowState, resultState;
    static boolean[] onlight, offlight, resultLight;
    static int onClick, offClick;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        nowState = br.readLine();
        resultState = br.readLine();
        onlight = new boolean[N];
        offlight = new boolean[N];
        resultLight = new boolean[N];

        for (int i = 0; i < N; i++) {
            onlight[i] = nowState.charAt(i) == '0' ? false : true;
            offlight[i] = nowState.charAt(i) == '0' ? false : true;
            resultLight[i] = resultState.charAt(i) == '0' ? false : true;
        }

        click();

        if (onClick == Integer.MAX_VALUE && offClick == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(Math.min(onClick, offClick));
        }

    }

    public static void click() {
        onClick = 1;
        offClick = 0;
        onlight[0] = !onlight[0];
        onlight[1] = !onlight[1];
        for (int i = 1; i < N; i++) {
            if (onlight[i - 1] != resultLight[i - 1]) {
                onlight[i - 1] = !onlight[i - 1];
                onlight[i] = !onlight[i];
                if (i + 1 < N) {
                    onlight[i + 1] = !onlight[i + 1];
                }
                onClick++;
            }

            if (offlight[i - 1] != resultLight[i - 1]) {
                offlight[i - 1] = !offlight[i - 1];
                offlight[i] = !offlight[i];
                if (i + 1 < N) {
                    offlight[i + 1] = !offlight[i + 1];
                }
                offClick++;
            }
        }

        if (onlight[N - 1] != resultLight[N - 1]) {
            onClick = Integer.MAX_VALUE;
        }
        if (onlight[N - 1] != resultLight[N - 1]) {
            offClick = Integer.MAX_VALUE;
        }
    }
}

결과