[백준] 2138번: 전구와 스위치 문제
1. 문제
1) 링크
2) 문제
N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는(1) 상태와 꺼져 있는 (0) 상태 중 하나의 상태를 가진다. i(1<i<N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 있는 전구는 켜지고, 켜져 있는 전구는 꺼지게 된다. 1번 스위치를 눌렀을 경우에는 1, 2번 전구의 상태가 바뀌고, N번 스위치를 눌렀을 경우에는 N-1, N번 전구의 상태가 바뀐다.
N개의 전구들의 현재 상태와 우리가 만들고자 하는 상태가 주어졌을 때, 그 상태를 만들기 위해 스위치를 최소 몇 번 누르면 되는지 알아내는 프로그램을 작성하시오.
3) 입력
첫째 줄에 자연수 N(2≤N≤100,000)이 주어진다. 다음 줄에는 전구들의 현재 상태를 나타내는 숫자 N개가 공백 없이 주어진다. 그 다음 줄에는 우리가 만들고자 하는 전구들의 상태를 나타내는 숫자 N개가 공백 없이 주어진다.
4) 출력
첫째 줄에 답을 출력한다. 불가능한 경우에는 -1을 출력한다.
더 자세한 문제의 제한과 입출력을 보기 위해서는 위의 링크로 들어가보자!
2. 풀이
이 문제는 두 가지 경우로 나누어서 풀어야 한다.
첫 번째 0번 스위치를 눌렀을 경우, 두 번째 0번 스위치를 누르지 않았을 경우로 나누어서 문제를 해결해준다.
왜냐하면 첫 번째 스위치만 결정해주게 되면, 자신의 왼쪽에 있는 칸을 바꿀 수 있는 것은 자신 스위치밖에 더 이상 존재하지 않기 때문이다.
다시 말해서, 왼쪽에서 오른쪽으로 가면서 한 칸씩 스위치를 검사하기 때문에 첫번째 스위치만 켜짐/꺼짐을 결정하면 1번 index의 칸 값을 바꿀 수 있는 스위치는 2번 스위치가 유일하다.
따라서 첫 번째 스위치가 켜졌을 경우와 꺼졌을 경우로 나누어서 문제를 해결해준다.
먼저 첫 번째 스위치가 켜졌을 경우에 시행을 한 뒤에 꺼졌을 경우에도 다음에 시행을 해준다. 주의할 점은 이렇게 순차적으로 코드를 써주게 되면, 두번째 경우인, 첫번째 스위치가 꺼졌을 경우를 할 때 첫번째 경우의 스위치 변화에 영향을 받기 때문에 입력배열을 똑같은 곳에다가 하나 더 저장해두는 것이 필요하다.
3. 코드
이것을 코드화한 것은 아래와 같다.
import java.util.*;
public class Main{
static int n;
static void change(int a[], int i){
a[i]=1-a[i];
a[i+1]=1-a[i+1];
if (i+2<=n-1){
a[i+2]=1-a[i+2];
}
}
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
int a[]=new int[n];
int b[]=new int[n];
String s=sc.next();
for(int i=0; i<n; i++){
a[i]=s.charAt(i)-'0';
}
s=sc.next();
for(int i=0; i<n;i++){
b[i]=s.charAt(i)-'0';
}
int c[]=new int[n];
for(int i=0; i<n;i++){
c[i]=a[i];
}
int count1=1;
//0번 스위치를 눌렀을 경우
a[0]=1-a[0];
a[1]=1-a[1];
for(int i=1; i<n; i++){
if (a[i-1]!=b[i-1]){
count1++;
change(a, i-1);
}
}
boolean first=true;
for(int i=0; i<n; i++){
if (a[i]!=b[i]){
first=false;
}
}
int count2=0;
//안눌렀을 경우
for(int i=1; i<n; i++){
if (c[i-1]!=b[i-1]){
count2++;
change(c, i-1);
}
}
boolean second=true;
for(int i=0; i<n; i++){
if (c[i]!=b[i]){
second=false;
}
}
if (!first && !second){
System.out.println(-1);
}
else if (!first){
System.out.println(count2);
}
else if (!second){
System.out.println(count1);
}
else{
System.out.println(Math.min(count1, count2));
}
}
}
두 번다 시행을 해준 뒤 해당 값이 일치하는지를 한 번 더 검사한 뒤 first/ second라는 boolean 자료형을 하나 만들었다. 만약 둘다 true라면 두 번 시행 모두 가능하다는 뜻이므로 둘 중에서 작은 값을 출력해주면 되고, 하나만 가능하다면 가능한 count 값을 출력해주면 된다. 만약 둘다 가능하지 않다면 문제의 요구사항대로 -1을 출력해준다.