[JAVA] 전구와 스위치 (백준 2138) ( 그리디)

www.acmicpc.net/problem/2138

2138번: 전구와 스위치

 

# 풀이

주어진 전구 배열을 arr2 라고 하고 만들어야할 전구배열을 goal 이라고 하자.

스위치는 0번부터 n-1번까지 있다.

 

arr2에서 0번 스위치를 누른 상태를 가진 전구배열을 arr1 이라고 하자.

 

즉 정리하면

0번 스위치를 누른 상태 = arr1 

0번 스위치를 누르지 않은 상태 = arr2 이다.

 

i= 1 ~ n-1

1) i 번 스위치를 누를지 말지 정해야한다. 따라서 arr1[i-1] 과 goal[i-1] 이 다르다면 i번 스위치를 누른다.

2) arr2[i-1] 과 goal[i-1] 이 다르다면 i번 스위치를 누른다.

 

arr1 과 goal 이 같은지 arr2와 goal이 같은지 확인하여 최소값을 갱신한다.

 

import java.util.*;

class Main{
    static int n;

    static boolean[] arr1,arr2,goal;

    static int cnt1=1;
    static int cnt2;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n =sc.nextInt();
        arr1 = new boolean[n];
        arr2 = new boolean[n];
        goal = new boolean[n];

        char[] temp;
        temp = sc.next().toCharArray();
        for(int i=0;i<n;i++){
            arr1[i] = temp[i]=='1';
            arr2[i] = temp[i]=='1';
        }
        temp = sc.next().toCharArray();

        for(int i=0;i<n;i++){
            goal[i] = temp[i]=='1';
        }



        swithOn(arr1,0);

        for(int i=1;i<n;i++){
            if(arr1[i-1] != goal[i-1]) {
                swithOn(arr1,i);
                cnt1++;
            }
            if(arr2[i-1] != goal[i-1]) {
                cnt2++;
                swithOn(arr2,i);
            }
        }

        int ret = checkAndReturn();
        System.out.println(ret==Integer.MAX_VALUE?-1:ret);


    }


    static void swithOn(boolean[] arr, int idx){
        for(int i=idx-1;i<=idx+1;i++){
            if(i>=0 && i<n){
                arr[i] = !arr[i];
            }
        }
    }

    static int checkAndReturn(){
        int ret = Integer.MAX_VALUE;
        boolean ok1 = true;
        boolean ok2 = true;

        for(int i=0;i<n;i++){
            if(arr1[i]!=goal[i]){
                ok1 = false;
            }
            if(arr2[i]!=goal[i]){
                ok2 = false;
            }
        }

        if(ok1) ret = cnt1;
        if(ok2) ret = Math.min(ret,cnt2);

        return ret;
    }
}