[백준 2138] 전구와 스위치(Java)

문제

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

풀이

그리디 알고리즘을 이용하는 문제이다.
1번째 전구를 켰을 때 경우와 키지 않았을 때 경우로 나누어서 최소 횟수를 구한다.
i-1번째 전구가 만약 만들고자 하는 전구의 i-1번째와 다른 상태일 경우 i번째 스위치를 작동시켜 i-1번째 전구의 상태를 바꾼다. 이 때 i, i+1번째 전구의 상태도 바뀐다.
i-1번째 전구의 상태에 따라 i번째 스위치를 작동시킬지가 결정이 되므로 굳이 작동 횟수를 구할 때 i-1번째 스위치로 다시 돌아갈 필요가 없다.

코드

import java.util.Scanner;

public class Main {

    public static void main(String args[]){
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        char[] init1 = new char[N];
        char[] init2 = new char[N];
        String str = scan.next();
        for(int i=0;i<N;i++){
            init1[i] = str.charAt(i);
            init2[i] = str.charAt(i);
        }

        char[] correct = new char[N];
        str = scan.next();
        for(int i=0;i<N;i++) correct[i] = str.charAt(i);

        int num1 = 0;
        int num2 = 0;

        init1[0] = switchChar(init1[0]);
        init1[1] = switchChar(init1[1]);
        num1++;

        for(int i=1;i<N-1;i++){
            if(correct[i-1]!=init1[i-1]){
                init1[i-1] = switchChar(init1[i-1]);
                init1[i] = switchChar(init1[i]);
                init1[i+1] = switchChar(init1[i+1]);
                num1++;
            }
            if(correct[i-1]!=init2[i-1]){
                init2[i-1] = switchChar(init2[i-1]);
                init2[i] = switchChar(init2[i]);
                init2[i+1] = switchChar(init2[i+1]);
                num2++;
            }
        }
        if(correct[N-2]!=init1[N-2]){
            init1[N-1] = switchChar(init1[N-1]);
            init1[N-2] = switchChar(init1[N-2]);
            num1++;
        }
        if(correct[N-2]!=init2[N-2]){
            init2[N-1] = switchChar(init2[N-1]);
            init2[N-2] = switchChar(init2[N-2]);
            num2++;
        }
        String init1Str = new String(init1);
        String init2Str = new String(init2);
        String correctStr = new String(correct);
        if(!init1Str.equals(correctStr)) num1 = Integer.MAX_VALUE;
        if(!init2Str.equals(correctStr)) num2 = Integer.MAX_VALUE;

        if(Math.min(num1, num2)==Integer.MAX_VALUE) System.out.println(-1);
        else System.out.println(Math.min(num1, num2));

    }
    public static char switchChar(char a){
        if(a=='0') return '1';
        return '0';
    }
}

느낀점

사실 이 문제는 처음에 1번째 전구를 킬 때와 안 킬때로 구분해서 풀어야된다는 사실을 몰랐어서 푸는데 오래걸렸다.
원래 그리디 알고리즘에서 조금 취약하다고 느꼈지만, 오늘 문제를 풀면서 더 그런 느낌을 받았다.
앞으로도 그리디 알고리즘을 더 열심히 풀어야겠다고 생각이 들었다.