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

문제 설명

N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 있는 전구는 켜지고, 켜져 있는 전구는 꺼지게 된다. 1번 스위치를 눌렀을 경우에는 1, 2번 전구의 상태가 바뀌고, N번 스위치를 눌렀을 경우에는 N-1, N번 전구의 상태가 바뀐다.

N개의 전구들의 현재 상태와 우리가 만들고자 하는 상태가 주어졌을 때, 그 상태를 만들기 위해 스위치를 최소 몇 번 누르면 되는지 알아내는 프로그램을 작성하시오.

 

문제 풀이

이 문제의 핵심은1. 첫 번째 전구가 켜져있는지, 꺼져있는지 경우를 나누는 것2. i를 기준으로 i-1번째가 만들고자 하는 상태의 i-1번째와 같은지 비교하는 것입니다.

 

i-1번째를 기준으로 비교해야하기 때문에 1번 스위치를 2가지 경우로 나눠서 비교해야하기 때문입니다.

 

현재 전구: 001011만들고자 하는 전구: 101011A번 케이스 - 첫 번째 전구 On: 111011 / 1번 <-스위치 변환횟수B번 케이스 - 첫 번째 전구 Off: 001011 / 0번 

 

i = 2일 때 B의 1번쨰와 만들고자 하는 수의 1번째 전구가 같지 않으므로 2번째 스위치를 눌러줍니다.

변환 전

변환 후

i = 3일 때 만들고자 하는 수의 2번째 전구와 A, B 케이스의 2번째 전구가 같지 않으므로 둘 다 변환해줍니다.

 

이런 식으로  N번째까지 변환을 해주었을 때 만들고자 하는 전구와 A, B 모두 같지 않다면 -1을 반환하고

그게 아니라면 A, B 중 제일 작은 변환 횟수를 반환해주시면 됩니다.

if(!isSame(status, light1)) ans1 = Integer.MAX_VALUE;
if(!isSame(status, light2)) ans2 = Integer.MAX_VALUE;

if(ans1 == Integer.MAX_VALUE && ans2 == Integer.MAX_VALUE) System.out.println(-1);
else System.out.println(Math.min(ans1, ans2));

ex) 000, 010

-> want: 010, A: (110, 1), B: (000, 0) //처음 변환 -> 첫 번째 전구가 켜져있는지 아닌지

-> want: 010, A: (001, 2), B: (000, 0) // 1번째 비교, 2번째 스위치 기준으로 변환

-> want: 010, A: (010, 3), B: (011, 1) // 2번째 비교, 3번째 스위치 기준으로 변환

-> A는 want와 같고 B는 같지 않으므로 3을 반환합니다.  

 

풀이 코드

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();

    static int N, ans1 = 0, ans2 = 0;
    static int[] light1, light2, status;

    private static void input() throws IOException {
        N = Integer.parseInt(br.readLine());
        light1 = new int[N+1];
        light2 = new int[N+1];
        status = new int[N+1];
        String line1 = br.readLine();
        String line2 = br.readLine();
        for(int i=0; i<line1.length(); i++){
            int num = Integer.parseInt(line1.substring(i, i + 1));
            light1[i+1] = num; light2[i+1] = num;
            status[i+1] = Integer.parseInt(line2.substring(i, i+1));
        }
    }

    private static void process() throws IOException{
        if(status[1] == 1){
            lightSwitch(light2, 1);
            ans2 +=1;
        }else{
            lightSwitch(light1, 1);
            ans1 +=1;
        }

        for(int i=2; i<=N; i++){
            if(status[i-1] != light1[i-1]){
                lightSwitch(light1, i); ans1+=1;
            }
            if(status[i-1] != light2[i-1]){
                lightSwitch(light2, i); ans2 += 1;
            }
        }

        if(!isSame(status, light1)) ans1 = Integer.MAX_VALUE;
        if(!isSame(status, light2)) ans2 = Integer.MAX_VALUE;

        if(ans1 == Integer.MAX_VALUE && ans2 == Integer.MAX_VALUE) System.out.println(-1);
        else System.out.println(Math.min(ans1, ans2));
    }

    private static void lightSwitch(int[] light, int n) {
        if(n != 1) light[n-1] = swap(light[n-1]);
        light[n] = swap(light[n]);
        if(n != N) light[n+1] = swap(light[n+1]);
    }

    private static int swap(int n){
        return n == 0 ? 1 : 0;
    }

    private static boolean isSame(int[] light, int[] status){
        for(int i=1; i<=N; i++)
            if(light[i] != status[i]) return false;
        return true;
    }

    public static void main(String[] args) throws IOException {
        input();
        process();
    }
}

 

<출처>

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

2138번: 전구와 스위치