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

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

2138번: 전구와 스위치

핵심

완전탐색을 하면 시간초과가 뜨게 된다. 따라서 다른 방법을 사용해야 한다.

그리디를 사용해서 풀면 쉽게 풀린다.

자기 자신의 스위치를 누르면 양옆과 본인의 스위치가 변한다.

0~n까지 이동할 때, i-1을 바꿀 수 있는 전구는 i 뿐이다.

즉 첫 번째 전구가 꺼진 경우와 켜진 경우 2가지를 나누어서 풀 수 있다.

 

 

정답 코드

import java.util.Scanner;

public class Main {
    static int N;
    static char[][] before;
    static char[] after;
    static int min = Integer.MAX_VALUE;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        before = new char[2][N];
        after = new char[N];
        before[0] = sc.next().toCharArray();
        after = sc.next().toCharArray();

        for (int i = 0; i < N; i++) before[1][i] = before[0][i];

        getBulb(0,1,0);

        turnOnOff(1,0);

        getBulb(1,1,1);
        System.out.println(min==Integer.MAX_VALUE?"-1":min);
    }

    public static void turnOnOff(int cur, int index){
        for (int i = index-1; i< index+2; i++){
            if (0<=i && i <N){
                before[cur][i] = before[cur][i]=='0'?'1':'0';
            }
        }
    }

    public static void getBulb(int cur, int index, int count){
        if (N==index){
            if (after[N - 1] == before[cur][N - 1]) min =  Math.min(min, count);
            return;
        }
        if (after[index-1] != before[cur][index-1]){
            turnOnOff(cur,index);
            getBulb(cur,index+1,count+1);
        }else getBulb(cur,index+1,count);
    }
}

해설

첫번째 전구를 끈 경우를 befor [0]라고 보고,  킨 경우를 before [1]라고 생각하였다.

getBulb를 보면 위에 설명 대로 i-1번째 요소가 같은지를 비교한다.

다를 경우 turnOnOff를 통해 스위칭을 해준다.

이렇게 마지막 n-1 번째가 동일한 경우에는 그때 최솟값을 넣어준다.

다음은 첫 번째를 키고 시작한다.

위와 동일하게 반복하여 최솟값을 찾으면 된다.

 

 

배운 점

첫 번째 전구를 킨 경우와 끈 경우를 생각해서 풀어야 하는데 이러한 생각을 하는 것이 쉽지 않았다.

문제를 보고, 어떠한 규칙이 있는지 찾는 연습이 필요하다고 생각된다.