[백준/자바] 2138 전구와 스위치

사진 클릭시 문제로 이동

---

문제

N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는(1) 상태와 꺼져 있는 (0) 상태 중 하나의 상태를 가진다. i(1<i<N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다.

즉, 꺼져 있는 전구는 켜지고, 켜져 있는 전구는 꺼지게 된다.

1번 스위치를 눌렀을 경우에는 1, 2번 전구의 상태가 바뀌고, N번 스위치를 눌렀을 경우에는 N-1, N번 전구의 상태가 바뀐다.

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

입력

첫째 줄에 자연수 N(2≤N≤100,000)이 주어진다.

다음 줄에는 전구들의 현재 상태를 나타내는 숫자 N개가 공백 없이 주어진다.

그 다음 줄에는 우리가 만들고자 하는 전구들의 상태를 나타내는 숫자 N개가 공백 없이 주어진다.

출력

첫째 줄에 답을 출력한다.

불가능한 경우에는 -1을 출력한다.

예제 입력 1

3
000
010

예제 출력 1 

3

---

설명

그리디 문제다.

brute force로 하면 시간초과가 발생한다.

"i(1<i<N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다." 는 설명처럼

자기 자신의 스위치를 누르면 자신을 기준으로 바로 양옆의 스위치의 상태만 변하게 된다.

static void turnOnOff(int cur, int ind) {
	for(int i = ind-1; i < ind+2; i++) {
		if(-1 < i && i < n) {
			before[cur][i] = before[cur][i]=='1'?'0':'1';
		}
	}
}

그렇게 0번째 인덱스부터 n까지 오른쪽으로만 이동한다고 생각해보자.

그렇다면 i-1를 바꿀수 있는 것은 i번째 전구밖에 없어진다.

따라서 시작은 0번째 전구를 켰을 경우와 껐을 경우 2가지로 나눌수 있다.

따라서 입력을 같은 값을 2번을 받고 위의 행의 경우 0번째 인덱스를 끈경우, 아래행의 경우 0번째 인덱스를 켠 경우로 할 수 있다.

 

코드