[백준] 2138 전구와 스위치 - Greedy / Java

• 문제 링크

2138번: 전구와 스위치

 

• 풀이 과정

n 개의 전구의 모든 값을 앞에서 부터 XOR 연산을 수행하여 모든 경우를 확인한다.

이때 1 ~ n 의 범위 내 i 번째 연산에 의해 i - 1 의 값이 최종적으로 결정되므로 두 배열의 i - 1 번째 값을 비교하며

0번째 연산의 수행 여부에 따라 1번째 연산의 수행 여부가 결정되므로 두 경우를 모두 수행한다.

 

재귀 함수의 깊이를 idx 변수, 연산의 횟수를 cnt 변수로 지정하고

input[idx - 1] != target[idx - 1] 일 시 swap 함수로 XOR 연산을 통해 범위 내의 값을 뒤집은 후,

idx + 1, cnt + 1 을 매개 변수로 전달하여 재귀 호출을 하며, 다시 swap 함수를 실행하여 원 상태로 복귀한다.

input[idx - 1] == target[idx - 1] 일 시 연산을 수행하지 않으므로 idx + 1, cnt 를 매개변수로 전달하여 재귀 호출한다.

 

input[n - 1] == target[n - 1] 일 시 최솟값을 갱신 후 함수를 빠져나가고

최솟값을 저장한 변수인 minCnt 값의 변화 여부에 따라 -1 또는 minCnt 를 정답으로써 출력한다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	static int n;
	static char[] input, target;
	static int minCnt = Integer.MAX_VALUE;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		n = Integer.parseInt(br.readLine());
		input = br.readLine().toCharArray();
		target = br.readLine().toCharArray();

		recur(1, 0);

		input[0] ^= 1;
		input[1] ^= 1;

		recur(1, 1);

		bw.write((minCnt == Integer.MAX_VALUE ? -1 : minCnt) + "\n");
		bw.flush();
	}

	private static void recur(int idx, int cnt) {
		if (idx == n) {
			if (input[idx - 1] == target[idx - 1])
				minCnt = Math.min(minCnt, cnt);

			return;
		}

		if (input[idx - 1] != target[idx - 1]) {
			swap(idx);
			recur(idx + 1, cnt + 1);
			swap(idx);
		} else
			recur(idx + 1, cnt);
	}

	private static void swap(int idx) {
		for (int i = idx - 1; i <= idx + 1; i++) {
			if (i >= 0 && i < n)
				input[i] ^= 1;
		}
	}

}