[백준] 2138번: 전구와 스위치 (Java)

1. 문제설명

N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져있거나 꺼져있는 상태이다. i번 스위치를 누르면 i-1, i, i+1 의 세 개의 전구 상태가 바뀐다. 현재 상태와 반대로 바뀐다.

N개의 전구들을 만들고자 하는 상태로 만들기 위해 스위치를 최소 몇 번 누르면 되는지 구하는 문제이다.

• 시간 제한: 2초
• 메모리 제한: 128MB

 

2. 접근 방식

• 그리디 알고리즘을 사용한다.
  • 첫 번째 전구부터 순차적으로 처리한다.
  • 각 단계에서 현재 전구의 왼쪽 전구가 목표 상태와 다르면 현재 스위치를 누른다.
• 첫 번째 스위치를 누르는 경우(curA)와 누르지 않는 경우(curB)를 고려한다.
  • 첫 번째 스위치의 상태가 이후의 모든 결정에 영향을 미치기 때문.
• 두 번째 전구부터 현재 상태와 목표 상태를 비교하며 진행한다.
  • i-1 번째 전구가 목표 상태와 다르면 i번째 스위치를 눌러야 한다.
  • 비트 연산(XOR)을 사용하여 전구 상태를 변경한다.
• 마지막 전구 상태를 확인해서 각 시나리오가 목표 상태를 달성했는지 파악한다.
• 두 가지 시나리오 중 누른 횟수가 적은 것을 선택하고, 둘 다 불가능하면 -1을 출력한다.

 

3. 최종 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine()); // 전구와 스위치 개수
        int[] curA = new int[n]; // 현재 전구 상태 저장
        int[] curB = new int[n]; // 현재 전구 상태 저장
        int[] result = new int[n]; // 만들고자 하는 전구 상태 저장

        String input = br.readLine();
        for(int i=0; i<n; i++) {
            curA[i] = curB[i] = input.charAt(i) - '0';
        }
        input = br.readLine();
        for(int i=0; i<n; i++) {
            result[i] = input.charAt(i) - '0';
        }

        // 첫번째 스위치를 누르는 경우와 누르지 않는 경우를 저장
        // curA의 첫번째 스위치를 누름
        curA[0] ^= 1;
        curA[1] ^= 1;
        int countA = 1, countB = 0;
        
        for(int i=1; i<n; i++) {
            // i-1 번째 전구가 목표 상태와 다르면 i번째 스위치를 누름
            if(curA[i-1] != result[i-1]) {
                curA[i-1] ^= 1; // 비트 연산으로 전구 상태 변경
                curA[i] ^= 1;
                if(i < n-1) curA[i+1] ^= 1;
                countA++;
            }
            if(curB[i-1] != result[i-1]) {
                curB[i-1] ^= 1;
                curB[i] ^= 1;
                if(i < n-1) curB[i+1] ^= 1;
                countB++;
            }
        }

        boolean possibleA = curA[n-1] == result[n-1];
        boolean possibleB = curB[n-1] == result[n-1];

        // 두 가지 경우 중 목표 상태와 같고 누른 횟수가 작은 것을 선택
        if(possibleA && possibleB) System.out.println(Math.min(countA, countB));
        else if(possibleA) System.out.println(countA);
        else if(possibleB) System.out.println(countB);
        else System.out.println(-1); // 둘다 불가능하면 -1
    }
}