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

문제 링크

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

알고리즘: 그리디

문제

N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 있는 전구는 켜지고, 켜져 있는 전구는 꺼지게 된다. 1번 스위치를 눌렀을 경우에는 1, 2번 전구의 상태가 바뀌고, N번 스위치를 눌렀을 경우에는 N-1, N번 전구의 상태가 바뀐다.

N개의 전구들의 현재 상태와 우리가 만들고자 하는 상태가 주어졌을 때, 그 상태를 만들기 위해 스위치를 최소 몇 번 누르면 되는지 알아내는 프로그램을 작성하시오.

풀이

두 가지 case로 나눌 수 있다.
1. 첫 번째 전구의 스위치를 눌렀을 때
2. 첫 번째 전구의 스위치를 누르지 않았을 때

두 가지 case를 따로 두고
2번째 전구부터 i-1의 전구가 기댓값과 같은지 다른지 check를 한다.
다르면 스위치를 눌러주고, 같다면 pass 해준다.
끝까지 check를 완료했다면 모든 값이 같은지 확인해준다.

소스 코드

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

public class Main {
    static final int dx[] = {-1,0,1};
    static int N,ans,cout;
    static int o_line[];
    static int c_line[];
    static int compare_line[];
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        o_line = new int[N];
        compare_line = new int[N];
        cout = 0;
        for(int i=0; i<2; i++) {
            String s = br.readLine();
            for(int j=0; j<N; j++) {
                if(i==0) {
                    o_line[j] = s.charAt(j) - '0';
                } else {
                    compare_line[j] = s.charAt(j) - '0';
                }
            }
        }
        c_line = o_line.clone();
        for(int i=0; i<2; i++) {
            for(int j=1; j<N; j++) {
                if(c_line[j-1] != compare_line[j-1]) {
                    change(j);
                    cout += 1;
                }
            }
            if(compare()) {
                ans = cout;
                break;
            } else {
                c_line = o_line.clone();
                change(0);
                cout = 1;
                ans = -1;
            }
        }
        System.out.println(ans);
    }
    
    static void change(int x) {
        for(int i=0; i<3; i++) {
            int nx = x + dx[i];
            if(nx>=0 && nx<=N-1) {
                if(c_line[nx] == 0) {
                    c_line[nx] = 1;
                } else {
                    c_line[nx] = 0;
                }
            }
        }
    }
    
    static boolean compare() {
        for(int i=0; i<N; i++) {
            if(c_line[i] != compare_line[i]) {
                return false;
            }
        }
        return true;
    }
}