[백준 / BOJ] 2138번 : 전구와 스위치 (JAVA)

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

2138번: 전구와 스위치

기본 아이디어

i번째 스위치를 누르면 i - 1, i, i + 1 세 개의 전구가 반전되기 때문에 언뜻 보기에 경우의 수가 많을 수 있다. i번째에 스위치를 누르러 갔을 때 상황은 8가지 중 하나일 것이다. 다음 표에서 X는 결과값과 다르다는 것이고, O는 같다는 의미이다.

i - 1번째 전구	i번째 전구	i + 1번째 전구
X	X	X
X	X	O
X	O	X
X	O	O
O	X	X
O	X	O
O	O	X
O	O	O

이렇게 경우의 수는 8가지지만, 사실 2 가지 경우만 생각해도 무방하다. i - 1번째 전구가 결과값과 같은지 아닌지이다. i번째, i + 1번째 전구의 경우에는 i + 1번째 스위치로도 조작이 가능하다. 즉 이번 i번째 스위치를 눌러서 다르게 바뀌었더라도, i + 1번째에서 수습이 가능한 것이다. 하지만 i - 1번째 전구는 이번에 맞추지 않는다면 영영 기회가 사라져버린다.

 

따라서 i번째 스위치를 누르는 기준은 i - 1번째 전구가 결과값과 같은지로 했다.

 

단, 애매한 경우가 하나 있다. 0번째 스위치는 0, 1번째 전구만 조작이 가능하고, i - 1번째 전구가 없다. 따라서 두 가지 경우를 모두 검사하도록 코드를 작성했다. 아래 코드에서 part1은 0번째 스위치를 누르지 않고 시작하는 경우, part2는 0번째 스위치를 누르고 시작하는 경우를 의미한다.

 

전체 코드

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		boolean[] one = new boolean[N];
		boolean[] two = new boolean[N];
		boolean[] result = new boolean[N];
		
		String light = br.readLine();
		for (int i = 0; i < N; i++) {
			one[i] = light.charAt(i) - '0' == 0 ? true : false;
			two[i] = one[i];
		}
		
		light = br.readLine();
		for (int i = 0; i < N; i++) {
			result[i] = light.charAt(i) - '0' == 0 ? true : false;
		}
		
		// part 1
		int cnt1 = 0;
		
		for (int i = 1; i < N - 1; i++) {
			if(one[i - 1] != result[i - 1]) {
				cnt1++;
				one[i - 1] = !one[i - 1];
				one[i] = !one[i];
				one[i + 1] = !one[i + 1];
			}
		}
		
		if(one[N - 1] != result[N - 1] || one[N - 2] != result[N - 2]) {
			cnt1++;
			one[N - 1] = !one[N - 1];
			one[N - 2] = !one[N - 2];
		}
		
		// part 2
		int cnt2 = 1;
		two[0] = !two[0];
		two[1] = !two[1];
		
		for (int i = 1; i < N - 1; i++) {
			if(two[i - 1] != result[i - 1]) {
				cnt2++;
				two[i - 1] = !two[i - 1];
				two[i] = !two[i];
				two[i + 1] = !two[i + 1];
			}
		}
		
		if(two[N - 1] != result[N - 1] || two[N - 2] != result[N - 2]) {
			cnt2++;
			two[N - 1] = !two[N - 1];
			two[N - 2] = !two[N - 2];
		}
		
		// 결과
		boolean f1 = true;
		boolean f2 = true;
		for (int i = 0; i < N; i++) {
			if(result[i] != one[i]) f1 = false;
			if(result[i] != two[i]) f2 = false;
		}
		
		if(!f1 && !f2) System.out.println(-1);
		else if(f1 && !f2) System.out.println(cnt1);
		else if(!f1 && f2) System.out.println(cnt2);
		else System.out.println(Math.min(cnt1, cnt2));
	}

}