28 May 2023

[Java] 백준 2138번: 전구와 스위치

2138

풀이 방법

greedy로 해결할 수 있다는 힌트를 보고 생각해봤다.

스위치를 누르면 양 옆의 전구를 포함해 3개의 전구의 상태가 뒤바뀐다. 하지만 첫 번째 전구와 마지막 전구는 한 쪽 옆면이 없기 때문에 2개의 상태만 바뀌고, 이를 활용하면 문제를 해결할 수 있다.

바로 기존 전구값과 / 기존 전구에서 첫 번째 버튼을 누른 값 두 개를 함께 결과 값과 비교해나가면 되는 것이다.

여기서 가장 중요한 점은 n번째 전구를 결과와 비교하고 다르면 n+1 전구의 버튼을 누른다는 것! 그렇게 하면 전구를 누르는 횟수를 최소로 잡을 수 있다.

예제를 통해 이해해보자. 주어진 값은 000, 만들어야 하는 결과는 010이다. 첫 번째 버튼을 누른 firstOn은 110으로 시작한다.

firstOff(기존값): 000
firstOn: 110

1번째 전구를 비교했을 때 firstOff는 같고, firstOn은 다르니 firstOn의 2번째 전구를 눌러준다.

firstOff: 000
firstOn: 001

2번째 전구를 비교했을 때 firstOff와 firstOn 둘다 다르니 3번째 전구를 눌러준다.

firstOff: 011
firstOn: 010

firstOn은 결과값과 같다! 누른 횟수는 (시작 시 + 2번) = 3이 정답이 된다.

풀이 코드

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

public class BOJ_2138_전구와_스위치 {
	static int N;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		char[] firstOff = br.readLine().toCharArray();
		char[] firstOn = Arrays.copyOf(firstOff, N);
		char[] out = br.readLine().toCharArray();
		int cntOff = 0, cntOn = 1;
		
		push(firstOn, 0);
		
		for(int i=1; i<N; i++) {
			if(firstOff[i-1] != out[i-1]) {
				push(firstOff, i);
				cntOff++;
			}
			if(firstOn[i-1] != out[i-1]) {
				push(firstOn, i);
				cntOn++;
			}
		}
		
		int res = Integer.MAX_VALUE;
		if(firstOff[N-1] == out[N-1]) {
			res = Math.min(cntOff, res);
		} else if(firstOn[N-1] == out[N-1]){
			res = Math.min(cntOn, res);
		} else {
			res = -1;
		}
		System.out.println(res);
	}
	
	private static void push(char[] in, int index) {
		if(index > 0) in[index-1] = (in[index-1] == '0') ? '1' : '0';
		
		in[index] = (in[index] == '0') ? '1' : '0';
		
		if(index < N-1) in[index+1] = (in[index+1] == '0') ? '1' : '0';
	}

}

Thank You For Reading

점점 강해지고 있습니다.