백준 2138번 - 전구와 스위치 / Java

문제

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

2138번: 전구와 스위치

방법을 생각해내는건 오래안걸렸는데 예외처리를 하는 과정에서 멘탈이 깨져서 시간이 좀걸렸다.

차분하게 하나씩 조건을 처리하니까 금방 풀린 어렵지 않은 문제.

 

알고리즘

1. 첫번째 스위치를 조작하고 나서 모든 스위치를 조작한다. 이때 i-1번째전구가 원하는 상태와 다를경우만 조작한다

2. 끝까지 조작을 마친후 상태를 검사해서 횟수를 저장한다

3. 첫번째 스위치를 조작하지않고 1~2번을 반복한다

4. 만약 최솟값이 처음설정값과 그대로라면 -1을 그게아니면 최솟값을 출력한다.

소스코드

/*
 * BOJ2138
 * 2020.02.01
 * Hyeonseong
 */
import java.util.*;    
public class BOJ2138 {
    public static void main(String[] args) {
        Solution s = new Solution();
    }
}
class Solution{
    int n;
    int min = Integer.MAX_VALUE;
    int a[],b[],copy[];
    public Solution() {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt(); scan.nextLine();
        a = new int[n];
        b = new int[n];
        copy = new int[n];
        char temp[] = scan.nextLine().toCharArray();
        for(int i=0;i<n;i++) {
            a[i] = temp[i]-'0';
            copy[i] = a[i];
        }
        temp = scan.nextLine().toCharArray();
        for(int i=0;i<n;i++) {
            b[i] = temp[i]-'0';
        }
        copy[0] = 1-copy[0];
        copy[1] = 1-copy[1];
        go(1,1);
        for(int i=0;i<n;i++) {
            copy[i] = a[i];
        }
        go(1,0);
        if(min == Integer.MAX_VALUE) {
            System.out.println("-1");
        } else {
            System.out.println(min);
        }
    }
    public void go(int now, int cnt) {
        if(now==n-1) {
            if(copy[now-1]!=b[now-1]) {
                copy[now-1] = 1-copy[now-1];
                copy[now] = 1-copy[now];
                cnt++;
            }
            if(check()) {
                min = Math.min(min, cnt);
            }
            return;
        }
        if(copy[now-1]==b[now-1]) {
            go(now+1,cnt);
        } else {
            for(int i=now-1;i<=now+1;i++) {
                copy[i] = 1-copy[i];
            }
            go(now+1,cnt+1);
        }
    }
    public boolean check() {
        for(int i=0;i<n;i++) {
            if(copy[i]!=b[i]) return false;
        }
        return true;
    }
}