[백준/JAVA] 2138번: 전구와 스위치

📖 문제

https://www.acmicpc.net/problem/2138

 

 

 

💡  풀이 방식

• 그리디

- 스위치의 성격 상(on/off) 매 순간의 선택이 최적의 선택이 될 수 있으므로 그리디 사용 가능.

 

1. 첫 번째 전구의 스위치를 [켜는 / 끄는] 경우를 모두 고려해야 한다.

2. 2~N번째 전구까지 반복하며, i-1번째 인덱스의 현재값 != i-1번째 인덱스의 기댓값이면 스위치를 켠다.

3. 1번의 2가지 경우 모두 불가능하다면 -1을 출력하고, 아니라면 2개 중 최솟값을 출력한다.

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static boolean[] goalArr;
    static int min = Integer.MAX_VALUE;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());
        String now = br.readLine();
        String goal = br.readLine();
        
        boolean[] b1 = new boolean[N];  // 1번 전구 스위치 켠 상태
        boolean[] b2 = new boolean[N];  // 1번 전구 스위치 끈 상태
        goalArr = new boolean[N];
        
        for(int i = 0 ; i < N ; i++) {
            b1[i] = now.charAt(i) != '0';
            b2[i] = now.charAt(i) != '0';
            goalArr[i] = goal.charAt(i) != '0';
        }
        
        // 1번째 전구 스위치 사용하지 않고 진행
        greedy(1, 0, b1);
        
        // 1번째 전구 스위치 사용하고 진행
        greedy(1, 1, useSwitch(0, b2));
        
        System.out.println(min == Integer.MAX_VALUE ? -1 : min);
    }
    
    private static void greedy(int idx, int cnt, boolean[] b) {
        if(idx == N) {
            if(b[idx-1] == goalArr[idx-1]) {
                min = Math.min(min, cnt);
            }
            return;
        }
        
        if(b[idx-1] != goalArr[idx-1])  // 같지 않으면 스위치 사용하기
            greedy(idx+1, cnt+1, useSwitch(idx, b));
        else    // 같으면 스위치 사용하지 않고 다음 인덱스로 넘어가기
            greedy(idx+1, cnt, b);
    }
    
    // 스위치 켜는 함수
    private static boolean[] useSwitch(int idx, boolean[] b) {
        for(int i = idx-1 ; i <= idx+1 ; i++) {
            if(0 <= i && i < N)
                b[i] = !b[i];
        }
        
        return b;
    }
}

 

 

 

➕ 다른 풀이 방식

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

 

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

 

 

---

💦 어려웠던 점

- 그리디임을 캐치하는 것

- 해결 아이디어를 생각해 내는 것,,

 

 

🧐 새로 알게 된 내용

- 해결 아이디어,,

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[JAVA] 백준 알고리즘 2138번 (전구와 스위치)

[알고리즘] 백준 2138 전구와 스위치 Java