2138 전구와 스위치 [JAVA]

문제 분석

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

N<=10만 인 범위에 대해, N개의 전구 N개의 스위치가 존재하며 i번째 스위치는 i-1,i,i+1 번째 전구의 상태를 반전시킨다.

가능한 최소의 스위치 조작으로 주어진 전구 배열을 정답 배열로 만들려하는데 이때 드는 비용(횟수)을 구하는 문제이다.

 

처음 시도한 풀이는 아래와 같다.

맨 마지막 2개의 전구에 대해서 그 앞의 전구까지 가능한 최소의 비용으로 스위치 조작을 해서 정답 배열과 일치시켜 오게 된다면 이를 3개짜리 전구를 조작하는 문제로 변경할 수 있다고 생각했다.

즉, 1010111000 -> 00000000 이런 배열에 대해서 결국에는 0 a b -> 0 0 0 이 상태가 되는 문제로 변경할 수 있게 된다.

따라서 3개의 전구에 대해서 각각 최소의 스위치 조작으로 정답 배열과 일치시킬 수 있다면 해당 횟수를, 없다면 -1을 리턴하는 방식으로 구현했었다.

 

여기서, 간과했던 부분은 010 -> 000처럼 변경되는 경우, X 부분 자체는 2k번 변경되기에 제 자리이지만 X 내부 (실제로는 n-4번째 인덱스의)값은 2k+1번 변경되어 실제로 X10 -> X00이 아닌 X*00이 된다.

 

결국 방법을 떠울리지 못해  머리를 끙끙 앓다가..

 

https://staticvoidlife.tistory.com/143

[그리디 알고리즘] 전구와 스위치

질문게시판을 보다 이분의 그림 설명 한방에 문제가 이해가 됐다.

 

결국 0번 스위치를 누르거나 안누르는 경우 2가지는 항상 존재하게 된다.

 

이때, 각각의 상황에서 0번 전구가 정답 전구와 동일한 상태인 경우가 있고 아닌 경우가 있게 된다.

만약, 0번 전구가 정답 전구와 다르다면, 정답을 만들기 위해선 1번 스위치를 반드시 켜야 한다.

 

마찬가지의 논리로 n-2번 전구까지 정답 전구와 일치시켰을 때

n-1번째 전구 (마지막 전구)가 정답 전구와 일치한다면 가능한 경우가 되고, 그렇지 않다면 불가능한 경우가 된다.

 

 

 

코드

import java.util.*;

public class Main {

    static char[] after;
    static int n;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = Integer.parseInt(sc.nextLine());

        char[] before = sc.nextLine().toCharArray();

        char[] befModified = new char[n];
        System.arraycopy(before, 0, befModified, 0, n);
        befModified[0] = swapChar(befModified[0]);
        befModified[1] = swapChar(befModified[1]);

        after = sc.nextLine().toCharArray();

        int originValue = getMinValue(before);
        int modValue = getMinValue(befModified);

        int ans = 0;

        if(originValue == Integer.MAX_VALUE && modValue == Integer.MAX_VALUE)
            originValue=-1;

        if(originValue > modValue)
            ans = modValue+1;
        else ans = originValue;

        System.out.println(ans);


    }

    private static int getMinValue(char[] before) {
        int changeCount = 0;
        for (int i = 1; i < n - 1; i++) {
            if(before[i-1] == after[i-1])
                continue;
            before[i] = swapChar(before[i]);
            before[i+1] = swapChar(before[i+1]);
            changeCount++;
        }

        if(before[n-2] != after[n-2]){
            changeCount++;
            before[n-1] = swapChar(before[n-1]);
        }


        return before[n-1] == after[n-1] ? changeCount : Integer.MAX_VALUE;
    }

    private static char swapChar(char c){
        return  c== '0' ? '1' : '0';
    }


}