[Java] 백준 2138번 : 전구와 스위치

문제

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

2138번: 전구와 스위치

 

 

풀이 과정

첫 번째 스위치의 상태가 정해지면, 나머지 전구를 꺼야하는지가 결정된다. 따라서 첫 번째 스위치를 눌렀을 때와 안 눌렀을 때 2가지 경우에 대해 최솟값을 반환한다.

각 스위치를 누를지 말지 결정하는 기준은 자기 앞의 값이 목표 상태와 같은지 보고 결정하면 된다.

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

public class Main {

    static int N;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        char[] now1 = br.readLine().toCharArray();
        char[] now2 = Arrays.copyOf(now1, N);
        char[] goal = br.readLine().toCharArray();

        //1번 스위치 안 눌렀을 때 vs 눌렀을 때
        now2[0] = (now2[0] == '0') ? '1' : '0';
        now2[1] = (now2[1] == '0') ? '1' : '0';
        int result = Math.min(switching(now1, goal, 0), switching(now2, goal, 1));

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

    public static int switching(char[] now, char[] goal, int res){
        for(int i=1; i<N-1; i++){
            if(now[i-1] != goal[i-1]){
                res++;
                for(int j=-1; j<=1; j++){
                    now[i+j] = (now[i+j] == '0') ? '1' : '0';
                }
            }
        }

        if(now[N-2] != goal[N-2]){
            res++;
            now[N-2] = (now[N-2] == '0') ? '1' : '0';
            now[N-1] = (now[N-1] == '0') ? '1' : '0';
        }

        if(now[N-1] == goal[N-1]){
            return res;
        }
        else{
            return Integer.MAX_VALUE;
        }
    }
}

 

 

결과