G2138. 전구와 스위치

문제

제출 코드

• 사용 알고리즘 : 그리디

그리디임을 알아도 풀기 힘들었던 문제. 스위치를 누를 때 바뀌는 부분이 세군데인데, 맨 앞과 맨 마지막 스위치를 누를 때는 두군데라서 풀기 어려웠다.

그냥 간단하게 맨 앞 스위치를 누르는 경우와 아닌경우 두가지를 모두 해보고 앞에서부터 결과값에 맞게 스위치를 눌러가면 된다.

package gold;

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

public class G2138_bulbAndSwitch {
	static int N;
	static char[] bulb;

	static void turn(int n) {
		for(int i=-1; i<=1; i++) {
			int now = n+i;
			if(now<0 || now>=N) continue;
			bulb[now] = (bulb[now]=='0') ? '1' : '0';
		}
	}

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		String origin = br.readLine();
		char[] result = br.readLine().toCharArray();

		int cnt = Integer.MAX_VALUE;
		for(int i=0; i<2; i++) {
			bulb = origin.toCharArray();
			int cnt_tmp = 0;

			if(i==1) {
				cnt_tmp++;
				turn(0);
			}

			for(int j=1; j<N; j++) {
				if(bulb[j-1] == result[j-1]) continue;
				turn(j);
				cnt_tmp++;
			}
			if(bulb[N-1] == result[N-1]) cnt = Math.min(cnt, cnt_tmp);
		}

		System.out.println(cnt==Integer.MAX_VALUE ? -1 : cnt);
	}

}