백준 2138 전구와 스위치 (Java)

 

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

 

1. 문제

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을 출력한다.

2. 풀이

개인적으로 꽤나 생각하기 어려운 문제였다. 이 문제는 그리디 알고리즘을 사용하여 풀 수 있다. 우선 i번 스위치를 누르면 i-1, i, i+1이 반전된다. 첫 번째 전구 배열에서 두 번째 전구 배열을 만들어야 하는 데, 전구는 켜고 끄는 상태만 존재하므로 처음부터 하나씩 살펴보면서 i-1번 전구가 목표 전구 배열의 것과 다를 경우 눌러주어 풀 수 있다. 이 이후의 스위치를 누름에 대해서는 i-1번 전구는 더 이상 바뀌지 않기 때문이다.

        //각각 첫 번째 스위치를 누르지 않았을 경우, 눌렀을 경우
        static int ans = 0;
        static int ans2 = 1;

        src = new boolean[n];
        src2 = new boolean[n];
        dest = new boolean[n];

        input = reader.readLine();
        for (int i = 0; i < n; i++) {
            if (input.charAt(i) == '1') {
                src[i] = true;
            }
        }

        System.arraycopy(src, 0, src2, 0, n);
        src2[0] = !src2[0];
        src2[1] = !src2[1];

        input = reader.readLine();
        for (int i = 0; i < n; i++) {
            if (input.charAt(i) == '1') {
                dest[i] = true;
            }
        }

우선 출발 전구를 누름, 누르지 않음에 따라 두 개의 배열을 선언해준다. 위의 풀이로 풀게 되면 첫 번째 전구에 대해서는 이전에 전구가 존재하지 않으므로 확인이 불가능하기 때문이다. src2는 첫 번째 전구를 누른 상태이므로 ans2는 1로 초기화한다.

        for (int i = 1; i < n; i++) {

            //src1의 전구 변경
            if (src[i - 1] != dest[i - 1]) {
                src[i - 1] = !src[i - 1];
                src[i] = !src[i];

                if (i + 1 < n) {
                    src[i + 1] = !src[i + 1];
                }
                ans++;
            }


            //src2의 전구 변경
            if (src2[i - 1] != dest[i - 1]) {
                src2[i - 1] = !src2[i - 1];
                src2[i] = !src2[i];

                if (i + 1 < n) {
                    src2[i + 1] = !src2[i + 1];
                }

                ans2++;

            }

        }

이제 각 전구를 돌면서 이전 전구가 목표 전구와 다를 경우 현재 전구에 위치한 버튼을 누른다. 단, 마지막 전구일 경우 그 오른쪽의 전구는 존재하지 않으므로 이를 처리해준다.

        if (src[n - 1] != dest[n - 1]) {
            ans = Integer.MAX_VALUE;
        }
        if (src2[n - 1] != dest[n - 1]) {
            ans2 = Integer.MAX_VALUE;
        }

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

출력 부분이다. 두 번째 전구부터 이전 전구에 대해 확인하여 맞춰주었으므로 전구 배열을 목표 전구로 맞출 수 있는지 여부는 마지막 전구의 동일 여부만 확인해주면 된다. 이후 둘 중 더 적게 스위치를 누른 경우를 출력해주면 된다.

3. 코드 전문

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

public class Main {

    static int n;

    //첫 번째 버튼을 누르지 않았을 경우, 눌렀을 경우
    static boolean[] src;
    static boolean[] src2;

    static boolean[] dest;

    //각각 첫 번째 스위치를 누르지 않았을 경우, 눌렀을 경우
    static int ans = 0;
    static int ans2 = 1;

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

        n = Integer.parseInt(reader.readLine());

        src = new boolean[n];
        src2 = new boolean[n];
        dest = new boolean[n];

        input = reader.readLine();
        for (int i = 0; i < n; i++) {
            if (input.charAt(i) == '1') {
                src[i] = true;
            }
        }

        System.arraycopy(src, 0, src2, 0, n);
        src2[0] = !src2[0];
        src2[1] = !src2[1];

        input = reader.readLine();
        for (int i = 0; i < n; i++) {
            if (input.charAt(i) == '1') {
                dest[i] = true;
            }
        }

        for (int i = 1; i < n; i++) {

            //src1의 전구 변경
            if (src[i - 1] != dest[i - 1]) {
                src[i - 1] = !src[i - 1];
                src[i] = !src[i];

                if (i + 1 < n) {
                    src[i + 1] = !src[i + 1];
                }
                ans++;
            }


            //src2의 전구 변경
            if (src2[i - 1] != dest[i - 1]) {
                src2[i - 1] = !src2[i - 1];
                src2[i] = !src2[i];

                if (i + 1 < n) {
                    src2[i + 1] = !src2[i + 1];
                }

                ans2++;

            }

        }

        if (src[n - 1] != dest[n - 1]) {
            ans = Integer.MAX_VALUE;
        }
        if (src2[n - 1] != dest[n - 1]) {
            ans2 = Integer.MAX_VALUE;
        }

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


    }
}