백준 26215 - 눈 치우기 (자바 - 그리디)

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

26215번: 눈 치우기

 

* 문제 요약

지난 밤 겨울숲에는 눈이 많이 내렸다. 당신은 숲의 주민들을 위해 눈이 오지 않는 동안 모든 집 앞의 눈을 치우고자 한다.

당신은 1분에 한 번씩 두 집을 선택해서 두 집앞의 눈을 각각 1 만큼 치우거나, 한 집을 선택해서 그 집앞의 눈을 1만큼 치울 수 있다.

모든 집 앞의 눈을 전부 치울 때까지 걸리는 최소 시간은 얼마일까

 

* 입력

첫 줄에 집의 수를 의미하는 정수 N (1 <= N <= 100) 이 주어진다.

다음 줄에는 각각의 집 앞에 쌓여있는 눈의 양을 나타내는 정수 ai (1 <= ai <= 2,000) 이 주어진다.

 

* 출력

모든 집 앞의 눈을 치우는데 최소 몇 분이 걸리는지를 출력한다.

24시간(1440분) 이 넘게 걸릴 경우 -1 을 출력한다.

 

* 예시

 

* 해결 과정

입력 받은 값을 배열에 저장하고 매 반복마다 내림차순 정렬하면서, 배열의 첫번째 값이 0 이 아닐 동안. 즉, 모든 집앞의 눈이 치워지지 않은 동안 계속 아래와 같은 로직을 수행하며 반복을 진행하였다.

1. 집의 갯수가 2개 이상인 경우

- 첫번째 인덱스의 집앞에 눈이 모두 치워지지 않은 경우 값을 1 감소시킨다.

- 두번째 인덱스의 집앞에 눈이 모두 치워지지 않은 경우 값을 1 감소시킨다.

-> 집의 갯수가 2개 이상인 경우엔 반드시 집 2개를 골라 눈을 치우도록 했다. 그래야만 눈을 치우는 횟수를 최소화 시킬 수 있기 때문이다.

2. 집의 갯수가 1개인 경우

- 첫번째 인덱스의 값을 1 감소시킨다.

 

위와 같은 과정을 거친 후 현재 반복횟수를 나타내는 변수인 result 값을 1 증가시키고, 배열을 다시 내림차순으로 정렬한 뒤 다음 반복으로 넘어갔다.

최종적으로 배열을 내림차순 한 뒤에 첫번째 인덱스의 값이 0 인 경우. 즉, 모든 집 앞의 눈이 모두 치워진 경우 반복문을 종료시킨 뒤 그때까지 수행된 반복문의 횟수가 1440 보다 작은 경우 result 값을 출력시키고, 만약 1440 보다 큰 경우 -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;
import java.util.Collections;

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());

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

        int result = 0;
        Arrays.sort(house, Collections.reverseOrder());
        while (house[0] > 0) {
            if (house.length > 1) {
                if (house[0] > 0) {
                    house[0] -= 1;
                }
                if (house[1] > 0) {
                    house[1] -= 1;
                }
            } else {
                house[0] -= 1;
            }

            result++;

            Arrays.sort(house, Collections.reverseOrder());
        }

        if (result > 1440) {
            bw.write(-1 + "\n");
        } else {
            bw.write(result + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

 

눈이 치워지지 않은 집 2곳을 확정적으로 찾기 위해 매 반복마다 내림차순 정렬을 반복했다.

그렇게 하여 아래와 같은 로직을 수행했다.

현재 상황에서 최적의 해답을 선택한다. -> 눈을 치우는 횟수를 최소화 하기 위해 배열의 첫번째, 두번째 인덱스의 값이 0 이 아닌 경우 두 곳의 값을 동시에 1씩 감소시킨다.

선택된 해답이 조건을 만족하는지 검사한다. -> 모든 집앞의 눈이 치워지지 않은 경우 위의 과정을 계속 반복한다.

 

위와 같은 과정을 통해 집앞의 눈을 치우는 횟수의 최소에 가까운 값을 구했으므로 그리디 알고리즘에 해당된다.