문제 - 2138

문제접근

매 순간에 최적의 선택을 해야되므로 그리디알고리즘을 사용할 수 있다.
그리디 알고리즘을 사용하면서 매 선택때마다 최적을 선택하지만 종합적으로 볼때에는 최적이라고 보장은 절대 할 수 없다.

문제를 보면 i번째의 스위치를 누르면 i-1, i, i+1의 전구가 on/off가 된다고한다.
예제를 보면 000 -> 010으로 만들어야된다.

초기상태 000에서 전구1부터 전구3까지 스위치를 ON하면 원하는 결과를 얻을 수 있다. 그래서 결과는 총 3번.

여기서 중요한 부분은 전구2 스위치를 키는 경우이다. 전구 2 스위치를 왜 사용해야되는지
를 생각해보면 이전 스위치의 상태가 목표로하는 스위치의 상태와 다르기 때문에 전구2 스위치를 통해 전구1의 상태를 변경할려고 했다.
그래서 현재 전구 스위치를 누를지 말지는 이전 전구의 상태와 목표로 하는 전구의 상태의 여부에 따라 달라지게 된다.

첫번째 전구를 누를지 말지는 아무도 예상을 하지 못한다. 그러므로 누른 경우하고 누르지 않은 경우를 따로 확인해야된다.

소스코드

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

public class Main {
    static int N;
    static int ans;
    public static void main(String[] args) throws  Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        ans = Integer.MAX_VALUE;

        String first = br.readLine();
        String goal = br.readLine();

        boolean switchA[] = new boolean[N];//첫번째 전구를 켠상태
        boolean switchB[] = new boolean[N];//첫번째 전구를 안 킨상태
        boolean goalAry[] = new boolean[N];

        for(int i=0;i<N;i++)
        {
            switchA[i] = first.charAt(i) != '0';
            switchB[i] = first.charAt(i) != '0';
            goalAry[i] = goal.charAt(i) != '0';
        }
        //첫번째 전구를 켠상태 시작
        process(1,1,usingSwitch(0,switchA),goalAry);
        //첫번째 전구를 키지 않고 시작
        process(1,0,switchB,goalAry);

        System.out.println(ans == Integer.MAX_VALUE ? -1 : ans);


    }
    public static void process(int idx, int count, boolean []arr,boolean []goal)
    {
        //모든 전구를 다 건드린 경우
        if(idx == N)
        {
            if(arr[idx -1] == goal[idx-1])
                ans = Math.min(ans,count);
            return;
        }

        //이전 전구의 상태가 다를 경우 목표와 같게 변경
        if(arr[idx -1] != goal[idx-1])
        {
            process(idx+1,count+1,usingSwitch(idx,arr),goal);
        }else{//목표와 같은 경우 변경X
            process(idx+1,count,arr,goal);
        }
    }

    //i-1, i , i+1 번째의 전구을 키거나 끌수있음
    public static boolean[] usingSwitch(int idx, boolean[] ary)
    {
        for(int i= idx -1; i<= idx+1;i++)
        {
            if(i>=0 && i<N)
            {
                ary[i] = !ary[i];
            }
        }
        return ary;
    }
}