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

문제

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

접근

스위치가 영향을 줄 수 있는 전구는 최소 2개이기 때문에 왼쪽에서부터 2개씩 끊어 완성시켜 나갈 수 있을 것이라고 생각했다.
만들고자 하는 전구 상태가 현재 상태와 같은 경우 or 다른 경우. 2가지 케이스를 놓고 경우의 수를 계산해보고자 하였으나 경우의 수가 너무 많고 특별한 규칙성을 찾지 못하였다.

결국 풀이를 참고하여 해결했고 아래 이해한 내용을 서술하겠다.

먼저, 내가 k번 전구의 상태를 바꾸려면

• k-1 or k+1번 스위치
• k번째 스위치

두 가지 선택지가 있다.

둘 중 하나를 선택하여 k번 전구의 상태를 픽스했다면 k+1, k+2 ... 번 전구의 상태만 맞추어주면 될 것이다. 그렇다면 1번 전구부터 시작하여 n번 전구까지 순차적으로 그리디적 접근이 가능하다.

하지만, 여기서 문제는 k번 전구의 상태를 픽스했다고 해도 k+1번 스위치를 누른다면 k번 전구에 영향을 미친다.

이 문제는 k번 전구를 컨트롤하기 위해 k+1번 스위치만 누른다고 생각하면 해결할 수 있다.
그렇게 하면, k+1번 전구를 컨트롤 하기 위해 k+1번 스위치를 눌러 k번 전구에 영향을 미치는 일이 없어지기 때문이다.

1번 전구를 컨트롤하는 1, 2번 스위치에서
1번 스위치의 누른다/안 누른다 정해준다면
2번 스위치만으로 1번 전구를 컨트롤할 수 있게 된다.
2번 스위치의 누른다/안 누른다 정해졌으니 2번 전구를 컨트롤할 땐 3번 스위치로 결정할 수 있다.

따라서 최초에 정해주지 않았던 1번 스위치를
i) 1번 스위치 누름
ii) 1번 스위치 안 누름
두 가지로 나누어 횟수를 구하고 비교하여 최솟값을 구하면 되겠다.

풀이

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

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

        int n = Integer.parseInt(br.readLine());

        String str = br.readLine();
        boolean[] start = new boolean[n]; // 전구 현재 상태
        for (int i = 0; i < n; i++) {
            if (str.charAt(i) == '1') start[i] = true;
        }

        str = br.readLine();
        boolean[] end = new boolean[n]; // 만들고자 하는 상태
        for (int i = 0; i < n; i++) {
            if (str.charAt(i) == '1') end[i] = true;
        }

        boolean[] state = start.clone();
        int cnt0 = solve(0, state, end, n);
        state = start.clone();
        int cnt1 = solve(1, state, end, n);

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

    public static int solve(int o, boolean[] start, boolean[] end, int n) {
        int cnt = 0;

        if (o == 1) {
            start[0] = !start[0];
            start[1] = !start[1];
            cnt++;
        }

        for (int i = 1; i < n - 1; i++) {
            if (end[i - 1] != start[i - 1]) {
                start[i - 1] = !start[i - 1];
                start[i] = !start[i];
                start[i + 1] = !start[i + 1];
                cnt++;
            }
        }

        if (end[n - 2] != start[n - 2]) {
            start[n - 2] = !start[n - 2];
            start[n - 1] = !start[n - 1];
            cnt++;
        }

        return (Arrays.equals(start, end)) ? cnt : Integer.MAX_VALUE;
    }
}

정리

추가적인 알고리즘, 자료구조를 사용하는 문제보다 이렇게 그리디 문제이지만 아이디어를 생각하기 어려운 문제가 정말 어렵다고 생각한다.
문제를 많이 풀어서 다양한 방법을 익혀야 할 것이다.