백준 15729 - 방탈출 (자바 - 그리디)

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

15729번: 방탈출

 

* 문제 요약

방탈출 게임을 하던 혜민이는 마지막 문제에 봉착했다. 단서는 다음과 같다.

1. 앞에는 일렬로 놓여진 N개의 버튼이 모두 불이 꺼진 상태로 있다.

2. 0 또는 1로 구성되어 있는 N자리 수가 적힌 쪽지가 있다.

3. 0은 불이 꺼진 버튼, 1은 불이 켜진 버튼을 뜻한다.

4. 불이 켜져 있는 버튼을 누르면 불이 꺼지고, 불이 꺼져 있는 버튼을 누르면 불이 켜진다.

5. 버튼을 누르면 그 버튼 뿐만이 아닌 오른쪽 두 개의 버튼도 같이 눌린다.

혜민이는 현재 모두 불이 꺼진 상태에서 버튼을 최소로 눌러서 쪽지와 똑같은 상태로 만들어야 한다는 것을 알아냈다.

혜민이를 도와줘서 방탈출 게임에 성공하자.

 

* 입력

첫째 줄에 N (1 <= N <= 1,000,000) 가 주어지고 둘째 줄에는 쪽지에 적혀있는 N자리의 수가 빈 칸을 사이에 두고 주어진다.

 

* 출력

눌러야 하는 버튼의 최솟값을 출력한다.

 

* 예시

 

* 해결 과정

문제에서는 모든 버튼의 불이 꺼져 있는 상태에서 입력으로 들어온 상태를 똑같이 만들어야 한다고 했으나, 실상 이 문제를 풀기 위해서는 입력받은 상태에서부터 역으로 시작하여 모든 불을 꺼뜨리는 식으로 진행시켰을 때 버튼을 총 몇번 눌러야 하는지를 확인해야 한다.

로직은 아래와 같이 설계했다.

1. 입력받은 버튼 상태 문자열을 배열에 하나씩 저장한 다음, 해당 배열에 1이 하나라도 존재하는 동안 반복문을 진행한다.

2. 배열을 처음부터 끝까지 순차탐색하며 1을 찾는다.

3. 만약 탐색 중 1이 발견될 경우 현재 탐색중인 버튼과 오른쪽에 있는 버튼 2개의 상태를 동시에 반대로 바꿔준 다음, 

(만약 현재 탐색중인 위치 상 오른쪽에 버튼이 2개 미만으로 존재하는 경우엔 오른쪽에 존재하는 버튼 한 개만 상태를 동시에 반대로 바꿔준다.) 버튼을 누른 횟수를 1 증가시킨다.

4. 위의 과정을 배열에 숫자 1이 하나도 존재하지 않을 때까지 반복하다가, 반복이 종료될 경우 버튼을 누른 횟수를 출력해준다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        new Main().solution();
    }

    private void solution() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int count = Integer.parseInt(br.readLine());
        String[] input = br.readLine().split(" ");
        int[] buttonArray = new int[count];
        for (int i = 0; i < buttonArray.length; i++) {
            buttonArray[i] = Integer.parseInt(input[i]);
        }

        int result = 0;
        while (Arrays.stream(buttonArray).anyMatch(x -> x == 1)) {
            for (int i = 0; i < buttonArray.length; i++) {
                if (buttonArray[i] == 1) {
                    buttonArray[i] = 0;
                    if (i <= buttonArray.length - 3) {
                        if (buttonArray[i + 1] == 1)
                            buttonArray[i + 1] = 0;
                        else
                            buttonArray[i + 1] = 1;

                        if (buttonArray[i + 2] == 1)
                            buttonArray[i + 2] = 0;
                        else
                            buttonArray[i + 2] = 1;
                    } else if (i == buttonArray.length - 2) {
                        if (buttonArray[i + 1] == 1)
                            buttonArray[i + 1] = 0;
                        else
                            buttonArray[i + 1] = 1;
                    }

                    result++;
                }
            }
        }

        bw.write(result + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

 

현재 상황에서 최적의 해답을 선택한다. -> 뒤에 어떤 데이터가 존재하든 상관없이 현재 탐색에서 1이 발견되면 현재 탐색중인 인덱스와 그 뒤에 있는 2개의 인덱스 상태를 반대로 뒤집어준다.

선택된 해답이 조건을 만족하는지 검사한다. -> 현재 배열에 숫자 1이 더 이상 존재하지 않을 때까지 위의 로직을 반복한다.

 

위의 과정을 통해 문제를 해결하였으므로 그리디 알고리즘 문제에 해당된다.