알고리즘 풀이 - 백준 2138(전구와 스위치, 그리디(Greedy))

 

관련글

 

그리디 알고리즘 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

N개의 스위치와 전구가 있을 때, 각 전구는 켜지거나(1) 꺼지거나(0)의 2가지 상태를 가지고 스위치를 누르면 자기 자신과 양 옆 스위치의 상태가 변할 때, N개의 전구를 특정 상태로 만들기 위해 눌러야 하는 스위치의 최소 횟수를 구하는 문제

 

 

2. 풀이

 

행렬 관련 문제와 유사하다.(관련 포스팅은 여기)

각 전구는 켜지거나 꺼지거나의 경우 뿐이므로 좌측 부터 체크하여 목표 상태와 값이 다른 경우 스위치를 눌러 주는 방식으로 해결이 가능하다.

 

그런데, 이 문제에서는 스위치를 누르면 자신 보다 좌측(이전) 위치에 있던 전구 또한 영향을 받기 때문에 가장 좌측의 있는 전구는 현재 위치와 바로 다음 위치의 스위치에 의해 값이 결정된다.

따라서, 가장 좌측의 있는 전구가 1번의 연산으로 결정되지 않기 때문에 누르거나 누르지 않거나의 2가지 연산에 대해 모두 체크를 해야 한다.

 

만약 스위치를 눌렀을 때, 이전의 전구는 영향이 없고 다음의 전구만 영향이 있는 문제였다고 가정하자.

그렇다면 다음과 같이 모든 스위치는 1회씩만 검사를 하면 된다.

즉, 각 위치에서 어떠한 선택을 하건, 다음 위치에서는 비교 결과에 따라 누르거나 누르지 않거나의 1회 연산으로 결정이 가능해진다.

 

 

그러나 현재 이 문제는 이전의 전구 또한 영향을 받기 때문에 변환 가능 최대 횟수는 다음과 같다.

 

따라서 첫 위치에서 누른 경우와 누르지 않은 경우를 모두 체크하여 결과가 같아지는 지를 검사해야 한다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

import java.io.*;

public class Main{
    static int n;
    static int[] bulb;
    static int[] target;
    public static void main(String[] args) throws IOException{
    
        // 주어진 정보를 저장한다.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        bulb = new int[n];
        target = new int[n];
        
        // s0는 시작 전구를 변경하지 않고 시작
        // s1은 시작 전구를 변경하고 시작
        int[] s0 = new int[n];
        int[] s1 = new int[n];
        
        String s = br.readLine();
        for(int i=0; i < n; i++){
            bulb[i] = s.charAt(i) - '0';
            s0[i] = s.charAt(i) - '0';
            s1[i] = s.charAt(i) - '0';
        }
        
        s = br.readLine();
        for(int i=0; i < n; i++){
            target[i] = s.charAt(i) - '0';
        }
        
        // a0는 s0의 배열에서 switch를 누른 횟수 - 0으로 시작
        // a1은 s1의 배열에서 switch를 누른 횟수 - 1로 시작
        int a0 = 0;
        int a1 = 1;
        
        for(int i=0; i < n; i++){
            // 제일 첫 위치에서는 s1 배열의 경우 0번째와 1번째를 변경하고 시작한다.
            if(i == 0){
                s1[i] = s1[i] ^ 1;
                s1[i+1] = s1[i+1] ^ 1;
            } else {
                // 현재 s0 배열의 비교 위치가 만들고자 하는 상태의 위치와 다른 상태라면
                if(s0[i-1] != target[i-1]){
                    // 스위치를 누른다.
                    change(s0, i);
                    
                    // 누른 횟수 +1
                    a0++;
                }
                
                // 마지막에 도달했는데 값이 다르다면 최대값으로 변경
                if(i == n-1 && s0[i] != target[i]) a0 = Integer.MAX_VALUE;
                
                // 현재 s1 배열의 비교 위치가 만들고자 하는 상태의 위치와 다른 상태라면
                if(s1[i-1] != target[i-1]){
                    // 스위치를 누른다.
                    change(s1, i);
                    
                    // 누른 횟수 +1
                    a1++;
                }
                
                // 마지막에 도달했는데 값이 다르다면 최대값으로 변경
                if(i == n-1 && s1[i] != target[i]) a1 = Integer.MAX_VALUE;
            }
        }
        
        // 둘 다 최대값이라면 변경이 불가능한 경우이므로 -1을 출력
        if(a0 == Integer.MAX_VALUE && a1 == Integer.MAX_VALUE){
            System.out.println(-1);
        // 그 외에는 더 작은 값을 출력
        } else {
            System.out.println(Math.min(a0, a1));    
        }
        br.close();
    }
    
    private static void change(int[] arr, int i){
        // 마지막 부분이라면 자신 이후는 변환이 불가하다.
        if(i == n-1){
            arr[i-1] = arr[i-1] ^ 1;
            arr[i] = arr[i] ^ 1;
        // 그 외의 모든 경우에는 양 옆 또한 변환을 시켜야 한다.
        } else {
            arr[i-1] = arr[i-1] ^ 1;
            arr[i] = arr[i] ^ 1;
            arr[i+1] = bulb[i+1] ^ 1;
        }
    }
}

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.