bj2138(전구와 스위치) - 그리디

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

그리디 문제는 항상 어렵다.

 

이번 그리디 문제는 초기 조건을 주고 생각하는 문제였다.

 

초기 조건을 불을 키고 시작하기

불을 안키고 시작하기

두 개로 나뉘어 그리디로 쭉쭉 불을 키고 끄면 되는 문제였다.

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

public class Main {
    static int N;
    static int[][] temp;
    static int[] will;
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException {
        initialize();
        System.out.println(setTemp());
    }

    private static int setTemp() {
        //0이 불을 안킨 로드맵
        int t0 = 0;
        //1이 불을 킨 로드맵
        int t1 = 1;
        change(0, 1);
        for(int i = 0; i < N-1; i++){
            if(temp[i][0] != will[i]){
                change(i+1, 0);
                t0++;
            }
            if(temp[i][1] != will[i]){
                change(i+1, 1);
                t1++;
            }
        }

        boolean t0_can = true;
        boolean t1_can = true;
        for(int i = N-2; i < N; i++){
            if(temp[i][0] != will[i]){
                t0_can = false;
            }
            if(temp[i][1] != will[i]){
                t1_can = false;
            }
        }

        if(t0_can && t1_can){
            return Math.min(t0, t1);
        }
        if(t0_can)return t0;
        if(t1_can)return t1;
        return -1;
    }

    private static void change(int index, int type){
        if(index == 0){
            temp[index][type] = Math.abs(temp[index][type] - 1);
            temp[index+1][type] = Math.abs(temp[index+1][type] - 1);
            return;
        }
        if(index == N-1){
            temp[index-1][type] = Math.abs(temp[index-1][type] - 1);
            temp[index][type] = Math.abs(temp[index][type] - 1);
            return;
        }
        if(index >= 1){
            temp[index-1][type] = Math.abs(temp[index-1][type] - 1);
            temp[index][type] = Math.abs(temp[index][type] - 1);
            temp[index+1][type] = Math.abs(temp[index+1][type] - 1);
        }
    }

    private static void initialize() throws IOException {
        N = Integer.parseInt(bufferedReader.readLine());
        temp = new int[N][2];
        will = new int[N];

        String temp_raw = bufferedReader.readLine();
        String will_raw = bufferedReader.readLine();
        for(int i = 0; i < N; i++){
            temp[i][0] = temp_raw.charAt(i) - '0';
            temp[i][1] = temp_raw.charAt(i) - '0';
            will[i] = will_raw.charAt(i) - '0';
        }
    }
}