2138번. 전구와 스위치

 

아이디어

i 번째 스위치를 누를 것인가 말 것인가는 i - 1번째 전구의 상태가 어떤가에 따라 결정된다.

 

i - 1 번째 전구의 상태가 만들고자 하는 전구의 상태와 동일하다면 i 번째 스위치를 누르면 안 되고

i - 1 번째 전구의 상태가 만들고자 하는 전구의 상태와 다르다면 i 번째 스위치를 눌러야 한다.

 

다만 가장 첫 번째 전구는 i - 1 번째 전구가 없기 때문에 가장 첫 번째 전구의 스위치를 누르지 않고 시작하는 케이스와

누르고 시작하는 케이스를 구분하여 2 가지 케이스에 대해 위의 규칙을 적용한다.

 

마지막 전구의 스위치까지 결정짓고 난 후에는 가장 마지막 전구의 상태가 만들고자 하는 전구의 상태와 동일한지 확인하여 가장 최소 회수를 구하면 된다

 

※ 0 ~ N -2 번째까지의 전구를 확인하지 않는 이유는 스위치를 누르는 과정 속에서 이미 목표하는 전구의 상태와 동일하게 맞춰줬기 때문에 마지막 전구의 상태에 따라 목표하는 전구의 상태로 만들 수 있냐 없냐가 결정되기 때문!!

 

 

풀이 코드

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

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

        int N = Integer.parseInt(br.readLine());
        String[] input1 = br.readLine().split("");
        String[] input2 = br.readLine().split("");

        int[] init1 = new int[N];
        int[] init2 = new int[N];
        int[] target = new int[N];

        for (int i = 0; i < N; i++) {
            init1[i] = Integer.parseInt(input1[i]);
            init2[i] = init1[i];
            target[i] = Integer.parseInt(input2[i]);
        }

        init2[0] = (init2[0] + 1) % 2;
        init2[1] = (init2[1] + 1) % 2;

        int cnt1 = 0; // init1 : 0번째 스위치 안 누른 상태
        int cnt2 = 1; // init2 : 0번째 스위치 누른 상태
        
        
        for (int i = 1; i < N; i++) {
            if (init1[i - 1] != target[i - 1]) { // i - 1번째 전구의 상태가 다르면 i 번째 스위치 눌러야 함
                init1[i] = (init1[i] + 1) % 2;
                if (i + 1 < N) {
                    init1[i + 1] = (init1[i + 1] + 1) % 2;
                }
                cnt1++;
            }

            if (init2[i - 1] != target[i - 1]) {
                init2[i] = (init2[i] + 1) % 2;
                if (i + 1 < N) {
                    init2[i + 1] = (init2[i + 1] + 1) % 2;
                }
                cnt2++;
            }
        }

        int result = -1;

        if (init1[N - 1] == target[N - 1] && init2[N - 1] == target[N - 1]) {
            result = Math.min(cnt1, cnt2);
        } else if (init1[N - 1] == target[N - 1]) {
            result = cnt1;
        } else if (init2[N - 1] == target[N - 1]){
            result = cnt2;
        }

        System.out.println(result);
    }
}