링크

전구와 스위치-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을 출력한다.

풀이

그리디문제는 풀면 풀수록 어려운것 같다...
이 문제를 보았을 때 어떤 식으로 할지 고민하다 구글링을 하니
그리디적 관점으로 보아야한다고 하더라!

우선 i번째를 선택하면 i-1, i, i+1이 바뀐다.
그리고 반복문이나 재귀함수를 통해 숫자는 점점 커져가며 종료가 되기에
만약 i번째를 바꿀 수 있는 마지막 부분은 i+1이 된다.

또한,
1) i-1 번째 전구를 두 번째 배열의 i-1 번째 전구와 비교하면서 스위치를 눌러야 할지 누르지 말아야 할지를 결정해서 최소한의 경우의 수를 구한다.
단, (2) 0 번째의 경우 -1 번째 전구는 없으니 0 번째를 눌렀을 경우와 누르지 않았을 경우를 비교하여 둘 중 하나의 경우에서 두 번째 배열과 똑같을 때 해당 경우에서 변경된 카운트를 출력하면 된다.

만약 두 경우 모두 (3) 두 번째 배열과 같지 않다면 해당 배열은 변경할 수 없기 때문에 -1을 출력한다.

Code

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

public class practice {
	public static int n;
	public static char[][] arr;
	public static char[] result;
	public static int answer=Integer.MAX_VALUE;
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		n=Integer.parseInt(br.readLine());
		String start=br.readLine();
		arr=new char[2][];
		//0번째 스위치를 눌렀는지 누르지 않았는지 비교하기 위해 2차원 배열에 2번 저장
		arr[0]=start.toCharArray(); //0번째 전구를 켜지 않는 경우
		arr[1]=start.toCharArray(); //0번재 전구를 키는 경우
		
		result=br.readLine().toCharArray();
		
		//arr[0] : 0번째 전구를 켜지 않는 경우
		play(1,0,0);
		System.out.println(answer);
		
		onoff(0,1); //arr[1] : 0번째 전구를 킨상태
		play(1,1,1);
		System.out.println(answer);
		
		System.out.println(answer==Integer.MAX_VALUE ? -1 : answer);
		
	}
	
	
	//전구의 전원을 스위치하는 기능
	public static void onoff(int idx, int type)
	{
		for(int i=idx-1; i<=idx+1; i++) //i-1, i, i+1 ->3개 바꾸기
		{
			if(i>=0 && i<n)
				arr[type][i]= (arr[type][i]=='1') ? '0' : '1';
		}
	}
	
	//answer=Integer.MAX_VALUE;
	public static void play(int idx, int type, int count)
	{
		if(idx==n)
		{
			if(arr[type][idx-1]==result[idx-1])
			{
				answer=answer>count ? count : answer;
			}
			return;
		}
		
		if(arr[type][idx-1]!=result[idx-1])
		{
			onoff(idx, type); //전구의 전원을 스위치한다.
			play(idx+1, type, count+1);
		}
		else
			play(idx+1, type, count);
	}
}