백준 2138번 전구와 스위치 (JAVA)

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

2138번: 전구와 스위치

 

 

저는 해당 문제를 슬라이딩 윈도우 개념을 활용하여 문제를 해결하였습니다.

저는 인덱스를 변화하는 전구의 맨 앞의 것을 잡았습니다. 문제에서 i를 저는 i-1로 잡았습니다.

이렇게 잡은 이유는 이렇게 설정하면 뒤의 행동이 앞의 상태를 변경하지 않게됩니다. 즉, i에서의 행동이 i이전의 배열에 영향을 주지 않습니다.

문제는 문제에서의 맨 앞의 전구를 키는 것은 어떻게 설정할 것인가 인데 이는 제가 임의로 isSwitch를 true를 줌으로써 해결하였습니다.

 

 

package BOJ.ETC;

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

public class BOJ_2138 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Function<String,Integer> stoi = Integer::parseInt;
        int n = stoi.apply(br.readLine());
        String command = br.readLine();
        int[] input = new int[n+1];
        int[] target = new int[n+1];
        for(int i = 0 ; i < n ; i++){
            input[i+1] = stoi.apply(command.charAt(i)+"");
        }
        command = br.readLine();
        for(int i = 0 ; i < n ; i++){
            target[i+1] = stoi.apply(command.charAt(i)+"");
        }
        boolean[] isSwitch = new boolean[n+1];
        int result = dfs(n,input,target,isSwitch);
//        System.out.println(result);
        isSwitch = new boolean[n+1];
        isSwitch[0] = true;
        result = Math.min(dfs(n,input,target,isSwitch),result);
        if(result == INF){
            System.out.println(-1);
        }else{
            System.out.println(result);
        }
    }
    static final int INF = Integer.MAX_VALUE;
    private static int dfs(int n , int[] input, int[] target, boolean[] isSwitch) {
        int cnt = 0;
        if(isSwitch[0]){
            cnt++;
        }
        boolean flag = true;
        for(int i = 1 ; i <= n ; i++){
            if(i == n ){
                if((input[i] + cnt) % 2 != target[i]){
                    flag = false;
                    break;
                }
            } else if( (input[i] + cnt) % 2 != target[i]){
                isSwitch[i] = true;
                cnt++;
            }
            if(i >= 2 && isSwitch[i-2]){
                cnt--;
            }
        }
        if(flag){
            int cntSwitch = 0;
            for(int i = 0 ; i < n ; i++){
                if(isSwitch[i]){
                    cntSwitch++;
                }
            }
            return cntSwitch;
        }else{
            return INF;
        }
    }
}