[백준][JAVA] BOJ 2138 전구와 스위치

 

문제 읽기 🤔

---

문제

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

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

입력

첫째 줄에 자연수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 전구들의 현재 상태를 나타내는 숫자 N개가 공백 없이 주어진다. 그 다음 줄에는 우리가 만들고자 하는 전구들의 상태를 나타내는 숫자 N개가 공백 없이 주어진다. 0은 켜져 있는 상태, 1은 꺼져 있는 상태를 의미한다.

출력

첫째 줄에 답을 출력한다. 불가능한 경우에는 -1을 출력한다.

예제 입력 1

3
000
010

예제 출력 1

3

 

 

문제 풀이📝

---

 

최적해를 구하는 그리디 문제이다.

1) 주어진 전구 상태를 목표 전구 상태로 만들기 위해 최소한으로 스위치를 눌러야 한다.

여기서 말하는 최소한이란, 스위치를 최대 한 번 누를 때를 말한다.

💡 💡 💡

여기에 (i - 1), i, (i + 1)번 전구가 있다.

(i - 1)번 스위치를 제외하고, (i - 1)번 전구에 영향을 주는 스위치는 i번 스위치 뿐이다.

i번 스위치를 눌러야 할까?

1) 현재의 (i - 1)번 전구가 목표하는 (i - 1)번 전구와 다르다면,

    -> i번째 버튼을 눌러 목표하는 상태로 바꾸어 주어야 한다.

2) 현재의 (i - 1)번 전구가 목표하는 (i - 1)번 전구와 같다면,

     -> 이미 목표하는 상태이므로 전구를 누를 필요가 없다.

스위치를 한 번 눌렀을 때의 상태는 세 번, 다섯 번... 눌렀을 때의 상태와 같다.

스위치를 누르지 않았을 때의 상태는 두 번, 네 번... 눌렀을 때의 상태와 같다.

고로 i번째 스위치는 최대 한 번만 누르거나 누르지 않아야 한다.

 

2) 스위치를 최대 한 번만 누를 경우의 결과 구하기

위의 증명 덕분에 우리는 (i - 1)번째 전구의 현재 상태를 (i - 1)번째 전구의 목표 상태와 비교하여 i번째 스위치를 누를 지 말 지 결정할 수 있게 되었다.

그러나 맨 처음 전구의 경우, 왼쪽에 아무 전구도 존재하지 않는다.

그렇기 때문에 이러한 예외상황을 처리해주어야 한다.

가능한 경우의 수는 1번 스위치를 누른다, 1번 스위치를 누르지 않는다 두 가지만 존재하기 때문에, 각각 알고리즘을 돌려 둘 중 스위치를 누른 횟수가 최소인 값을 선택하면 된다.

 

구현🛠️

---

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

public class Main {

    static final int INF = Integer.MAX_VALUE / 1000;
    static int N;
    static boolean[] origin;
    static boolean[] target;


    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        origin = new boolean[N + 2];
        target = new boolean[N + 2];

        String[] originInput = br.readLine().split("");
        String[] targetInput = br.readLine().split("");
        for (int i = 1; i <= N; i++) {
            origin[i] = originInput[i - 1].equals("1");
            target[i] = targetInput[i - 1].equals("1");
        }

        // 첫번째 버튼을 누르지 않은 경우
        boolean[] copied = copy();
        int result1 = getResult(copied);

        // 첫번째 버튼을 누른 경우
        copied = copy();
        pushSwitch(1, copied);
        int result2 = getResult(copied) + 1;

		// 첫번째 버튼을 눌렀을 때, 누르지 않았을 때의 값 중 최솟값 선택
        int min = Math.min(result1, result2);
        System.out.println(min == INF ? -1 : min);
    }

    private static int getResult(boolean[] lightBulbs) {

        int result = 0;
        for (int i = 2; i <= N; i++) {
			
            // idx 기준 왼쪽 전구의 현재상태와 왼쪽 전구의 목표상태가 다르다면
            if (lightBulbs[i - 1] != target[i - 1]){
            	// 스위치를 눌러 왼쪽 전구를 목표 상태로 만든다
                pushSwitch(i, lightBulbs);
                result++;
            }
        }

		// 원하는 상태가 만들어진 경우 -> 스위치를 누른 횟수 반환
        if (isSame(lightBulbs)){
            return result;
        }

		// 원하는 상태가 만들어지지 않은 경우 -> INF값 반환
        return INF;
    }


	// idx번째 스위치를 눌렀을 때
    private static void pushSwitch(int idx, boolean[] lightBulbs) {
		// (idx - 1), idx, (idx + 1)번째 스위치의 상태 변경
        lightBulbs[idx - 1] = !lightBulbs[idx - 1];
        lightBulbs[idx] = !lightBulbs[idx];
        lightBulbs[idx + 1] = !lightBulbs[idx + 1];
    }

	// 현재 전구 상태가 목표 전구 상태와 같은지 비교
    private static boolean isSame(boolean[] lightBulbs) {
        for (int i = 1; i <= N; i++){
            if (lightBulbs[i] != target[i]){
                return false;
            }
        }
        return true;
    }

    private static boolean[] copy() {

        return Arrays.copyOf(origin, origin.length);
    }

}

 

 

실행 결과✅

---