[백준 - 2138][Gold 5] - 전구와 스위치 (JAVA)

문제 링크

---

https://www.acmicpc.net/problem/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을 출력한다.

 

구현으로 풀릴까??

---

우선 가장 쉬운 방법인 구현을 생각해보자. 전구는 총 N개 있으므로 모든 전구를 킬까 말까 2번의 선택지가 존재한다. 그러므로 시간 복잡도는 다음과 같다.

 

O(n) = (모든 전구를 고르는 조합)
= 2^n

 

N은 최대 100,000이기 때문에 최대 연산 횟수는 2^100,000이다. 이는 제한시간인 2초의 추정 연산 횟수인 2억보다 훨신 큰 값이므로 제한 시간 내로 해결할 수 없다. 우리는 다른 방법을 찾아야 한다.

 

DP로 풀릴까??

---

최소 횟수라고 하니 DP로 풀릴수 있을까 고민해보자.

 

DP로 풀기 위해선 전구의 경우를 쪼개서 생각해야 하는데 전구를 1개씩 켜는 것이 아니라 인접한 3개의 전구를 동시에 키고 끄기 때문에 현재의 선택이 다음의 전구의 경우의 수에 영향을 끼치기 때문에 문제를 쪼개어 생각할 수 없다. 우리는 다른 방법을 찾아야 한다.

 

그리디로 풀릴까??

---

이제 최후의 방법인 그리디를 생각해보자

 

그리디로 문제를 해결하기 위해선 현재 맞지 않은 전구를 똑같이 맞추면 된다. 다시말하면 시작~현재의 전구의 형태를 목표 전구의 시작~현재의 모양과 맞추면 된다. 그러므로 현재 스위치를 작동할 때 이전 전구에 영향을 끼치면 안된다. 그러므로 i번째가 아니라 i+1번째의 스위치를 누르면 이전 선택한 전구의 모양을 건들지 않고 원하는 전구만 바꿀 수 있다!

 

하지만 이렇게 하면 i+1번째부터 탐색하므로 첫번째인 인덱스 0번째는 탐색할 수 없게된다. 그러므로 0번째를 누른 경우와 0번째를 누르지 않은 경우를 동시에 탐색해 둘 중 맞는 것을 선택하면 문제를 해결할 수 있다!

 

문제 코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        char[] bulbs = br.readLine().toCharArray();	
        char[] pressFirstBulbs = Arrays.copyOf(bulbs,bulbs.length); //첫번째 전구를 누른 경우의 수
        
        //1번째 스위치를 눌러 전구 모양 번경
        pressFirstBulbs[0] = bulbs[0] == '1' ? '0' : '1';;
        pressFirstBulbs[1] = bulbs[1] == '1' ? '0' : '1';;

        char[] target = br.readLine().toCharArray();

        int count = 0;	//첫번째 스위치를 안 누른 경우의 수
        int pressFirstCount = 1; //첫번째 스위치를 누른 경우의 수

		//i번째의 전구를 확인해서 다르면 같도록 변경		
        for(int i=1;i<bulbs.length;i++){
           //첫번째 전구를 안누른 경우의 전구 변경
            if(bulbs[i-1] != target[i-1]){
                bulbs[i-1] = bulbs[i-1] == '1' ? '0' : '1';
                bulbs[i] = bulbs[i] == '1' ? '0' : '1';

                if(i+1 < bulbs.length){
                    bulbs[i+1] = bulbs[i+1] == '1' ? '0' : '1';
                }

                count++;
            }
			//첫번째 전구를 누른 경우의 전구 변경
            if(pressFirstBulbs[i-1] != target[i-1]){
                pressFirstBulbs[i-1] = pressFirstBulbs[i-1] == '1' ? '0' : '1';
                pressFirstBulbs[i] = pressFirstBulbs[i] == '1' ? '0' : '1';

                if(i+1 < pressFirstBulbs.length){
                    pressFirstBulbs[i+1] = pressFirstBulbs[i+1] == '1' ? '0' : '1';
                }

                pressFirstCount++;
            }
        }
        
        //모든 경우의 수 중 맞는 것의 회수를 출력
        if(isSame(bulbs,target)){
            System.out.println(count);
        }else if(isSame(pressFirstBulbs,target)){
            System.out.println(pressFirstCount);
        }else{
            System.out.print(-1);
        }
    }
	
    //2개의 배열이 같은지 확인하는 메소드
    public static boolean isSame(char[]a, char[]b){
        for(int i=0;i<a.length;i++){
            if(b[i] != a[i]){
                return false;
            }
        }

        return true;
    }
}

 

실행 결과

---

 

 

제한시간인 2초 안에 문제가 해결되었다!

 

키워드

---

• 최소 횟수
  
  • 구현, DP, 그리디의 가능성을 가지고 있다.

 

팁

---

• 놓치는 경우의 수가 있다면 해당 경우의수를 넣고 한번 더 풀이 로직을 실행는 것도 좋은 방법이다.
• 현재의 선택이 과거 딱 맞추어 놓은 경우의 수를 망치지 않도록(영향을 끼치지 않도록) 선택하자