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

[CMSSKKK]

TITLE

전구와 스위치

LINK

• 문제 출처 사이트 : 백준
• Link

📷 Screenshots

댓글 양식

• 아래 양식을 복사한 뒤 [shift]+[tab] 2회를 하고 작성하여 주세요

    ### 풀이 언어

    - python/java

    ### 코드

    ```python/java

    ```

    ### 핵심 로직 혹은 자료구조

    - 

    ### 시간 복잡도

    - O(  )

[CMSSKKK]

풀이 언어

• java

코드

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

public class Main {

    private static int n;
    private static char[][] current;
    private static char[] expect;
    private static int answer;

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

        n = Integer.parseInt(br.readLine());
        answer = n + 1;
        current = new char[2][n];
        String bulbs = br.readLine();
        String result = br.readLine();

        current[0] = bulbs.toCharArray();
        current[1] = bulbs.toCharArray();
        expect = result.toCharArray();

        change(0, 1, 0);
        click(1, 0);
        change(1,1,1);
        if(answer == n + 1) {
           answer = -1;
        }
        System.out.println(answer);
    }

    private static void click(int sequence, int index) {
        for (int i = index -1; i <= index +1; i++) {
            if(i < 0 || i >= n) {
                continue;
            }
            if(current[sequence][i] == '1') {
                current[sequence][i] = '0';
            } else {
                current[sequence][i] = '1';
            }

        }

    }

    private static void change(int sequence, int index, int count) {
        if(index == n) {
            if (current[sequence][n - 1] == expect[n - 1]) {
                answer = Math.min(answer, count);
            }
            return;
        }

        if (current[sequence][index - 1] != expect[index - 1]) {
            click(sequence, index);
            change(sequence, index + 1, count + 1);
        } else {
            change(sequence, index + 1, count);
        }
    }
}

핵심 로직 혹은 자료구조

• 그리디

시간 복잡도

• O( )