[백준 2138] 전구와 스위치 - JAVA // le_effort

전구와 스위치

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	2905	1088	864	38.936%

문제

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 복사

xxxxxxxxxx
3
000
010

예제 출력 1 복사

3

 

 

 

풀이

 

핵심 아이디어 : i-1번째 전구는 i번째 스위치에서 최종 결정가능하다.

 

정해진 모양으로 만들기 위해서 현재 i번째 스위치는 i-1번째 전구값을 결정 할 수 있는 마지막 수단입니다.

따라서 0~N-1 까지의 스위치를 차례대로 켜보는데 현재 5번스위치에 있다면

5번스위치에서 4번전구의 값을 최종으로 결정 할 수 있고 여기서 바꿔야 하는 모양과 같이 나와야합니다.

 

이 개념을 가지고 a배열과 b배열을 2가지로 진행하였습니다.

 

첫번째 스위치를 키느냐 마느냐의 유무로 나뉘는 배열인데요

예를들어 전구를 000에서 001로 만들어야 한다면

 

첫번째 스위치를 안켰을때는 001을 만들지 못합니다.

 

첫번째 스위치를 켰을때는 110

마저 두번째 스위치를 키면 001

 

이를 코딩으로 구현하기 위해서 첫번째 스위치를 켰을때와 안켰을때 배열을 2개 만들어서 해줘야 하며

a배열과 b배열의 [n-1]번째 원소값이 바꿔야 하는 배열의 [n-1]번째 값과 같다면 두 배열이 일치하다는 걸 알 수 있습니다.

 

 

xxxxxxxxxx
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
​
public class Main {
    static int n;
    static char[] origin;
    static char[] change;
    static char [] a;
    static char [] b;
    public static void main(String[] args) throws  IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        n = Integer.parseInt(br.readLine());
        
        change = br.readLine().toCharArray();
        origin = br.readLine().toCharArray();
        
        
        a = new char[change.length];
        b = new char[change.length];
        int a_cnt = 0;
        int b_cnt = 0;
        
        for(int i=0; i<change.length; i++) {
            a[i] = change[i];
            b[i] = change[i];
        }
​
        
        
        // a 배열 안키고 그냥 간 것
        // b 배열 키고 간 것
        change(0,b[0]);
        b_cnt++;
        
        for(int i=1; i<n; i++) {
            if(a[i-1]!= origin[i-1]) {
                change(i,1);
                a_cnt++;
            }
            if(b[i-1]!=origin[i-1]) {
                change(i,2);
                b_cnt++;
            }
        }
        int ans = Integer.MAX_VALUE;
        if(a[n-1]==origin[n-1]) {
            ans = Math.min(ans, a_cnt);
        }
        if(b[n-1]==origin[n-1]) {
            ans = Math.min(ans, b_cnt);
        }
        
        if(ans == Integer.MAX_VALUE) {
            System.out.println(-1);
        }
        else {
            System.out.println(ans);
        }
    }
    public static void change(int idx, int arr_num) {
        if(arr_num==1) {
            
            int before = idx-1;
            int now = idx;
            int next = idx+1;
            
            int tmp = a[now];
            
            // 자기 자신 스위치
            if(tmp=='0') {
                a[now] = '1';
            }
            else {
                a[now] = '0';
            }
            
            if(before>=0) {
                tmp = a[before];
                
                if(tmp=='0') {
                    a[before] = '1';
                }
                else {
                    a[before] = '0';
                }
            }
            if(next<n) {
                tmp = a[next];
                if(tmp=='0') {
                    a[next] = '1';
                }
                else {
                    a[next] = '0';
                }
            }
            
            
            
            
        }
        else {
            int before = idx-1;
            int now = idx;
            int next = idx+1;
            
            int tmp = b[now];
            
            if(tmp =='0') {
                b[idx]='1';
            }
            else {
                b[idx] = '0';
            }
​
            if(before>=0) {
                tmp = b[before];
                
                if(tmp=='0') {
                    b[before] = '1';
                }
                else {
                    b[before] = '0';
                }
            }
            if(next<n) {
                tmp = b[next];
                if(tmp=='0') {
                    b[next] = '1';
                }
                else {
                    b[next] = '0';
                }
            }
        }
    }
}
​