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

문제

N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 있는 전구는 켜지고, 켜져 있는 전구는 꺼지게 된다. 1번 스위치를 눌렀을 경우에는 1, 2번 전구의 상태가 바뀌고, N번 스위치를 눌렀을 경우에는 N-1, N번 전구의 상태가 바뀐다.

N개의 전구들의 현재 상태와 우리가 만들고자 하는 상태가 주어졌을 때, 그 상태를 만들기 위해 스위치를 최소 몇 번 누르면 되는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 전구들의 현재 상태를 나타내는 숫자 N개가 공백 없이 주어진다. 그 다음 줄에는 우리가 만들고자 하는 전구들의 상태를 나타내는 숫자 N개가 공백 없이 주어진다. 0은 켜져 있는 상태, 1은 꺼져 있는 상태를 의미한다.

출력

첫째 줄에 답을 출력한다. 불가능한 경우에는 -1을 출력한다.

예제 입력 1

3
000
010

예제 출력 1

3

 

소스코드

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

public class Main {

	private static BufferedReader br;
	private static StringTokenizer st;
	
	private static int N, result=-1;
	private static char[] s1, s2, tmp;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		br=new BufferedReader(new InputStreamReader(System.in));
		N=Integer.parseInt(br.readLine());
		s1=new char[N];
		s2=new char[N];
		tmp=new char[N];
		
		String ss1=br.readLine();
		String ss2=br.readLine();
		for(int i=0;i<N;i++) {
			s1[i]=ss1.charAt(i);
			s2[i]=ss2.charAt(i);
		}
		
		// 0번 안 누름
		int cnt=0;
		for(int i=0;i<N;i++) tmp[i]=s1[i];
		for(int i=1;i<N;i++) {
			if(tmp[i-1]!=s2[i-1]) {	// 숫자가 다르면 전구 상태 변경
				cnt++;
				toggle(i);
			}
		}
		if(tmp[N-1]==s2[N-1]) result=cnt;	// 마지막 숫자가 다르면 불가능한 경우
		
		// 0번 누름
		for(int i=0;i<N;i++) tmp[i]=s1[i];
		toggle(0);
		cnt=1;
		for(int i=1;i<N;i++) {
			if(tmp[i-1]!=s2[i-1]) {	// 숫자가 다르면 전구 상태 변경
				cnt++;
				toggle(i);
			}
		}
		if(tmp[N-1]==s2[N-1]) {	// 마지막 숫자가 다르면 불가능한 경우
			if(result==-1) result=cnt;
			else result=Math.min(result, cnt);
		}
		System.out.println(result);
	}

	private static void toggle(int idx) {	// 0->1, 1->0 숫자 변경
		for(int i=idx-1;i<=idx+1;i++) {
			if(i>=0 && i<N) {
				if(tmp[i]=='0') tmp[i]='1';
				else tmp[i]='0';
			}
		}
	}
	
}

첫번째 스위치를 눌렀을 때와 누르지 않았을 때로 구분하여 생각해줍니다.

각각의 경우에 i-1번째 전구의 상태를 확정지었으므로, i번째 전구에 영향을 줄 수 있는 것은 i+1번째 전구밖에 없습니다. 다음 전구의 상태를 최종 상태와 비교하며 다른 경우 스위치를 누르고, 같으면 누르지 않습니다. 마지막 전구가 같으면 스위치를 누른 횟수를 저장해주고, 다르면 저장하지 않습니다.

첫번째 스위치를 눌렀을 때와 누르지 않았을 때 중 스위치를 더 적게 누른 경우를 찾아줍니다.