[백준][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. 첫 번째 스위치를 on/off 로 두가지 케이스로 나누어서 구한다.
2. 그렇게 된다면 i-1 on/off의 결정은 i로만 결정하게된다.
3. 2~N 까지 반복을 한 뒤 마지막 스위치를 확인한다.
4. 만약에 마지막 원소끼리 같다면 바꿀 수 있고, 같지 않다면 바꿀 수 없다.
   그렇게 두가지 케이스로 나온 것 중에 최소 값을 출력한다.
   (만약에 초기에 설정해둔 Integer.MAX_VALUE라면 바꿀 수 없는 값이기 때문에 -1을 출력한다.)

🎈코드

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

public class Main {
    static int N;
    static char[][] curState;
    static char[] changeState;
    static int answer = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        curState = new char[2][N];
        curState[0] = br.readLine().toCharArray();
        changeState = br.readLine().toCharArray();


        // curState[0] : 첫 번째 스위치 off
        // curState[1] : 첫 번째 스위치 on
        for(int i=0; i<N; i++){
            curState[1][i] = curState[0][i];
        }

        function(0,0);

        // 첫 번째 스위치 on
        change(1,0);

        function(1,1);

        answer = answer==Integer.MAX_VALUE?-1:answer;
        System.out.println(answer);
    }
    static void change(int cur, int index){
        for(int i=index-1; i<=index+1; i++){
            if(0<=i && i<changeState.length) {
                curState[cur][i] = curState[cur][i] == '0' ? '1' : '0';
            }
        }
    }
    static void function(int cur,int count){
        for(int i=1; i<N; i++){
            if(curState[cur][i-1] != changeState[i-1]){
                change(cur,i);
                count++;
            }
        }
        if(curState[cur][N-1] == changeState[N-1]){
            answer = Math.min(answer, count);
        }
    }
}