이번에 풀어본 문제는
백준 2138번 전구와 스위치 입니다.

📕 문제 링크

❗️코드

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

public class Main {
    static int N;
    static boolean [][] map;
    static boolean [] dest;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        String tmp = br.readLine();
        map = new boolean[2][N];
        dest = new boolean[N];
        for(int i = 0; i < N; ++i)
        {
            boolean b = tmp.charAt(i) == '1';
            map[0][i] = b;
            map[1][i] = b;
        }
        tmp = br.readLine();
        for(int i = 0; i < N; ++i) dest[i] = tmp.charAt(i) == '1';

        for(int i = 0; i < 2; ++i) map[0][i] = !map[0][i]; // 0 1 누름

        int answer = Integer.MAX_VALUE;
        int cnt = 1;
        for(int t = 0; t < 2; ++t)
        {
            for(int i = 1; i < N-1; ++i)
            {
                if(map[t][i-1] != dest[i-1])
                {
                    press(t,i);
                    cnt++;
                }
            }
            if(map[t][N-2] != dest[N-2])
            {
                map[t][N-2] = !map[t][N-2];
                map[t][N-1] = !map[t][N-1];
                cnt++;
            }
            if(map[t][N-1] == dest[N-1]) answer = Math.min(answer,cnt);
            cnt = 0;
        }
        if(answer == Integer.MAX_VALUE) answer = -1;
        System.out.print(answer);
    }
    static void press(int idx, int num)
    {
        for(int i = num-1; i < num+2; ++i) map[idx][i] = !map[idx][i];
    }
}

📝 풀이

나란히 놓인 N개의 전구와 N개의 스위치가 있다고 했을 때, N번째 스위치를 누르면 N-1,N,N+1의 전구가 on/off 되는 조건입니다.
처음 입력된 전구의 상태를 주어진 결과로 만들기 위해 누를 수 있는 스위치 횟수의 최솟값을 구하는 문제입니다. 불가능한 경우는 -1을 출력합니다.
먼저 두 가지 상황으로 놓고 볼 수 있는데 첫 번째 스위치를 누르는가 누르지 않는가 입니다.
그 이유를 설명해보면, 먼저 각 전구들의 상태에 영향을 미칠 수 있는 인덱스는 자기 자신과 자신 이전의 인덱스입니다.(N-1,N) 따라서 1번 스위치부터 순차적으로 탐색할때, N-1번 전구의 상태를 비교하여 N번 스위치를 누를지 말지를 판단해주면 순차적으로 결과에 접근할 수 있습니다. 위 방법을 적용하기 위해서는 0번 인덱스부터 확정을 짓고 시작해야 하므로, 1번 스위치(인덱스는 0)를 누른 경우와 누르지 않은 경우 두가지로 분류하여 모두 탐색해 주면 해결할 수 있습니다.
실행과정은 어렵지 않으므로 생략하겠습니다.

📜 후기

구현은 쉽지만 해결방법을 생각하기가 굉장히 어려웠던 문제입니다.
구글링을 통해 아이디어를 얻었는데, 다음에 비슷한 문제가 나온다면 쉽게 풀어낼 수 있을 것 같습니다!^^