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

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

 

문제 접근하는데 2틀정도 걸렸다.

 

원래는 이렇게 풀면 안돼고 30분 정도 고민해서 안나오면 풀이를 보고 넘어가야되는데 이번 문제는 왠지 내손으로 풀어보고 싶었다.

 

하지만 도무지 풀 방법이 생각이 나지 않아 해답을 보고 문제를 풀었다.

 

먼저 내가 했던 시행착오에 대해 먼저 설명하겠다.

 

1. 모든 스위치를 누르는 순열에 대하여 풀이 - 이 방법은 N의 갯수가 10만이기 때문에 애초에 불가능해서 포기하였다.

 

2. 스위치를 누르는 순서는 중요하지 않다 -> 어떤 스위치를 누르느냐만 결정하면됨 -> 조합 - 마찬가지로 N의 갯수가 10만이기 때문에 불가능한 해답이었다.

 

이후로는 그리디 하게 푸는 방법, 이진탐색으로 스위치를 누르는 횟수를 결정한 뒤 푸는 법, dfs 로 분기처리, 가지치기를 하는법을 생각하였지만 정답을 풀 수 있는 방법은 떠올리지 못했다.

 

해답은 이렇다.

 

그리디 + 2분기 문제인데 맨 처음 스위치를 누르느냐 누르지 않느냐 딱 2가지 경우에 대해서 그리디하게 풀면 되는 문제이다.

 

이유는 전구의 상태를 보았을때 스위치 i를 누르면 i - 1, i, i + 1 전구가 바뀌므로 결국 순차적으로 앞부터 어떤 스위치를 눌러야할지 말지 결정할때 마지막으로 결정되는 것은 i 번째 스위치에서 결정난다.

 

때문에 스위치를 눌러야하는데 강제되지만 처음 스위치에 대한 경우만 다르다. 0번 전구, 1번 전구가 있다고 했을때 0번 전구의 영향을 주는 스위치는 0번 스위치 1번 스위치 이므로 0번스위치를 눌러야하나 말아야하나 두가지 분기에 대하여 나머지는 0번 전구의 결과에 따라 1번 스위치를 순차적으로 결정하면된다.

 

그리고 마지막에 전구의 결과에 따라 이 경우가 가능한지 가능하지 않은지 판단하면된다.

 

import java.io.*;
import java.util.*;

public class Main {
    static int N, ans1, ans2;
    static int[] x1, x2, y;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        x1 = new int[N];
        x2 = new int[N];
        y = new int[N];

        String str = br.readLine();
        for(int i = 0; i < N; i++){
            x1[i] = x2[i] = str.charAt(i) - '0';
        }

        str = br.readLine();
        for(int i = 0; i < N; i++){
            y[i] = str.charAt(i) - '0';
        }

        // 1. 0번 스위치를 누르지 않는 경우
        ans1 = 0;
        for(int i = 1; i < N; i++){
            if(x1[i - 1] != y[i - 1]){
                ans1++;
                pushSwitch(x1, i);
            }
        }

        // 2. 0번 스위치를 누르는 경우
        ans2 = 1;
        pushSwitch(x2, 0);

        for(int i = 1; i < N; i++){
            if(x2[i - 1] != y[i - 1]){
                ans2++;
                pushSwitch(x2, i);
            }
        }

        boolean z1 = x1[N - 1] == y[N - 1];
        boolean z2 = x2[N - 1] == y[N - 1];
        
        if(z1 && z2){
            System.out.println(Math.min(ans1, ans2));
        }else if(!z1 && !z2){
            System.out.println(-1);
        }else{
            if(z1){
                System.out.println(ans1);
            }else{
                System.out.println(ans2);
            }
        }
    }
    static void pushSwitch(int[] x, int i){
        if(i == N - 1) {
            x[i - 1] = (x[i - 1] + 1) % 2;
            x[i] = (x[i] + 1) % 2;
        }else if(i == 0){
            x[i] = (x[i] + 1) % 2;
            x[i + 1] = (x[i + 1] + 1) % 2;
        }else{
            x[i - 1] = (x[i - 1] + 1) % 2;
            x[i] = (x[i] + 1) % 2;
            x[i + 1] = (x[i + 1] + 1) % 2;
        }
    }
}

 

정답은 나왔지만 풀이가 좀 아쉬워서 GPT 피드백을 받아보았다.

 

다른건 뭐 별로 도움은 안되었는데 pushSwtich를 하는 함수에서 N = 1 일 경우에 오류가 생길수 있는 부분이 있었다. (i == 0일때 x[1]을 접근하기 때문에 OutOfRange 가 발생할 수 있음.)

문제에서는 N 의 범위가 2<= N <= 10만 이기 때문에 정답으로 처리되었고 문제가 발생하진 않았지만 다른 문제를 풀 때 충분히 발생할 수 있는 부분이라 고치기로 하였다.

 

함수를 분리해서 분기처리하는 방식으로 바꿔보았다.

static void pushSwitch(int[] x, int i){
    toggle(x, i - 1);
    toggle(x, i);
    toggle(x, i + 1);
}
static void toggle(int[] x, int idx){
    if(idx < 0 || idx >= N) return;
    x[idx] = (x[idx] + 1) % 2;
}

 

범위문제도 해결하고 가독성도 좋아지는 코딩 스킬인거 같다.