3월 19, 2024

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

1. 문제

1) 링크

www.acmicpc.net/problem/2138

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을 출력해준다.