BOJ - 전구와 스위치 2138번 (JAVA)

❓ 문제 - 백준 전구와 스위치 2138번 - JAVA 풀이법

 

출처 

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

2138번: 전구와 스위치

 

 

📝 문제해결법

1. 이 문제는 그리디(탐욕)법으로 풀었다.

• 우선 왼쪽 -> 오른쪽으로 스위치를 켜면서 지나가면 첫 번째 전구와 마지막 전구만 두 번의 영향을 받으며, 나머지 전구들은 총 3번의 영향을 받게 된다. => 스위치를 켜면(* 범위 내에서) 현재위치-1, 현재위치, 현재위치+1의 영향을 주기 때문이다.
• 따라서 첫 번째 전구를 켜놓은 상태와 켜놓지 않은 상태로 나눈 후 왼쪽 -> 오른쪽으로 이동하면서 스위치를 켤지 말지 선택한다.
• 따라서 첫 번째 전구를 켜놓은 상태에서 두 번째 전구부터 마지막 전구까지 for문을 통해 돌면서 현재 (현재 위치 -1) 전구가 현재 내가 목표로 하는 전구 상태 (현재위치-1) 와 같다면 스위치를 키지 않고, 다르다면 스위치를 키면서 상태를 변경해준다. 스위치를 킬 때마다 킨 횟수를 카운트 증가시켜준다. 2번째 전구부터 마지막 전구까지 이와 같은 변화를 준 후, 마지막 전구가 내가 목표로 하는 전구상태의 마지막 전구와 상태가 같다면 카운트 증가횟수와 최솟값을 비교한다. (==> 마지막 전구를 왜 비교 ?? 어차피 첫 번째 전구 ~ 마지막-1 전구까지 다 내가 원하는 상태로 변경시켜줬기 때문에 마지막만 비교하면 됨)
• 첫 번째 전구를 켜지 않은 상태에서 위 방법과 같이 두 번째 전구부터 마지막 전구까지 스위치를 킬지 말지 정하며 전구의 상태를 변화시켜준다. 그리고 마지막 전구를 내가 원하는 전구상태의 마지막과 비교하며 같다면 스위치를 누른 횟수를 정답 최솟값과 갱신한다.
• 만약 정답 최솟값이 한번도 갱신되지 않은 상태라면 위 두 경우 모두 원하는 상태로 전구를 변화시키지 못하므로 -1 출력, 최솟값이 갱신되었다면 그 구해진 최솟값을 출력한다.

2) 느낀점

• 그리디 문제를 많이 안 풀어봐서... 많이 어렵다.. 많은 문제를 접해보면서 그리디 방식의 풀이법을 익숙해지자.
• 두 경우로 나눠서 풀었는데, 나는 두 경우 중 한 경우만 원하는 전구상태로 변화시킨다라고 인식하여 최솟값 갱신을 구하지 못했다. 그래서 자꾸 100%에서 틀렸습니다. 떠서 왜 그럴까 계속 고민하며 여러 블로그를 참고하니... 두 가지 경우로 전구 상태를 변화 시켜도 둘 다 원하는 전구 상태로 변화가능함... (그러니 카운트의 최솟값을 출력 하도록 했어야.....)
• 그리디 많이 친해지자 !^^

 

 

💻 소스코드 (구현)

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

public class Main {
    public static int[] dx = {-1, 0, 1};
    public static int n;
    public static char[] data1;
    public static char[] data2;
    public static char[] data3;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        String input1 = br.readLine();
        String input2 = br.readLine();
        data1 = new char[n];
        data2 = new char[n];
        data3 = new char[n];

        for(int i=0;i<n;i++){
            data1[i] = input1.charAt(i);
            data2[i] = data1[i];
            data3[i] = input2.charAt(i);
        }

        int ans = Integer.MAX_VALUE;

        int cnt1 = 0;
        int cnt2 = 0;

        data1 = change(data1, 0);
        cnt1++;

        for(int i=1;i<n;i++){
            if(data1[i-1] != data3[i-1]){
                data1 = change(data1, i);
                cnt1++;
            }
        }

        if(data1[n-1] == data3[n-1]){
            ans = Math.min(ans, cnt1);
        }

        for(int i=1;i<n;i++){
            if(data2[i-1] != data3[i-1]){
                data2 = change(data2, i);
                cnt2++;
            }
        }

        if(data2[n-1] == data3[n-1]){
            ans = Math.min(ans, cnt2);
        }


        if(ans == Integer.MAX_VALUE){
            System.out.println(-1);
        } else{
            System.out.println(ans);
        }






    }

    public static char[] change(char[] data, int i){
        for (int d = 0; d < 3; d++) {
            int nx = i + dx[d];
            if (nx < 0 || nx > n - 1) {
                continue;
            }

            if (data[nx] == '0') {
                data[nx] = '1';
            } else {
                data[nx] = '0';
            }
        }
        return data;
    }
}