중요하거나 어려웠던 문제에 대해서 작성합니다.

그리디 알고리즘(Greedy Algorithm)

골드 5이지만 처음 발상이 어려웠던 문제였습니다. 그 아이디어만 생각하면 사실 구현은 쉬운데, 그 아이디어를 떠올리는게 쉽지 않았습니다.

문제 📝 (Gold 5)

문제 링크는 다음과 같습니다.
https://www.acmicpc.net/problem/2138

접근방법

두 가지 아이디어를 생각해야 됩니다.

1. i-1 전구가 현재상태와 원하는 상태가 서로 다른 경우 i 스위치를 누름
2. 첫 스위치를 누르는 경우와 누르지 않는 경우 두가지로 진행

스위치 조작

스위치를 누를 때, i-1 전구를 키고 끄는 것을 결정하는 스위치는 i-2, i-1, i입니다. 즉, i 스위치를 넘어간다면, 그 다음부터는 i-1 전구를 조작할 수 있는 방법이 존재하지 않습니다.

그리고 다른 케이스(i-2, i-1 스위치 조작)의 경우에는 i-1 전구 뿐만이 아니라 그 앞에 있는 전구의 결과도 조작이 되게 됩니다. 하지만 i 스위치를 조작하는 경우에는 뒤쪽이 물론 바뀌긴 하지만, 진행됨에 따라 어차피 뒤쪽 스위치로 또 상태를 바꿀 수 있기 때문에 괜찮습니다.

첫 스위치 조작

첫 스위치는 i-1번째 전구가 애초에 없기 때문에 이를 조작하는 것이 없고, 다만 그 뒤에 있는 전구를 추가적으로 조작을 할 뿐입니다.

다른 스위치랑 다른 특성 때문에 이는 케이스를 분리를 해줍니다.

Java ☕️

import java.io.*;

public class Main {
	private static int ans = -1;
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        String before = br.readLine();
        String after = br.readLine();
        
        boolean[] light = new boolean[n];
        for(int i = 0; i < n ; i++) {
        	light[i] = before.charAt(i) != after.charAt(i);
        }
        // 첫 스위치를 누르지 않는 케이스
        change(light, 0);
        // 첫 스위치를 누르는 케이스
        light[0] = !light[0];
        light[1] = !light[1];
        change(light, 1);
        
        System.out.println(ans);
        br.close();
    }
    
    // 하나라도 다른게 있다면(true 존재) false, 모두 같으면 true
    public static boolean check(boolean[] arr) {
    	for(boolean e : arr) {
    		if(e) return false;
    	}
    	return true;
    }
    
    // i-1 전구를 보면서 i 스위치를 누를지 말지를 판단
    public static void change(boolean[] arr, int start) {
    	int cnt = start;
    	boolean[] test = arr.clone();
    	
    	for(int i = 1; i < test.length; i++) {
        	if(!test[i - 1]) continue;
        	
        	test[i - 1] = !test[i - 1];
        	test[i] = !test[i];
        	if(i != test.length - 1) {
        		test[i + 1] = !test[i + 1];
        	}
        	cnt++;
        }
    	
        // 모두 일치할시에는 check(test)가 true
    	if(check(test)) {
        	// ans == -1인 경우는 무조건 값 업데이트
    		ans = (ans == -1) ? cnt : Math.min(cnt, ans);
    	}
    }
}