백준 14469 - 소가 길을 건너간 이유3 (자바 - 그리디)

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

14469번: 소가 길을 건너간 이유 3

 

* 문제 요약

존의 농장에 방문할 수 있는 소들이 있는데, 존의 농장에 들어가는 문은 하나밖에 없고 그 문을 통과하려면 감시관의 길고 긴 검문을 받아야 한다.

여러마리의 소가 한번에 들어가려고 하면 줄이 그만큼 길어진다.

N 마리의 소가 이 농장에 방문하러 왔다. 소가 도착한 시간과 검문받는데 걸리는 시간은 소마다 다르다. (물론 같을 수도있다.)

두 소가 동시에 검문을 받을 수는 없다.

 

예를 들어 한 소가 5초에 도착했고 7초동안 검문을 받으면, 8초에 도착한 그 다음 소는 12초 까지 줄을 서야 검문을 받을 수 있다.

모든 소가 농장에 입장하려면 얼마나 걸리는지 구해보자.

 

* 입력

첫 줄에 100 이하의 양의 정수 N 이 주어진다. 다음 N 줄에는 한 줄에 하나씩 소의 도착 시각과 검문 시간이 주어진다.

각각 1,000,000 이하의 양의 정수이다.

 

* 출력

모든 소가 농장에 입장하는데 걸리는 최소 시간을 출력한다.

 

* 예시

 

* 해결 과정

전체의 최적 해를 구하고자 한다면 상대적으로 늦게 도착한 소가 있다고 해도 처리 시간을 계산해봤을 때 늦게 도착한 소를 먼저 들여보내는게 맞을 수도 있으나

그리디 방식으로 문제를 풀 경우 빨리 도착한 소를 기준으로 처리를 해주되, 도착한 시간이 같을 경우 처리시간이 더 짧은 소를 먼저 들여보내주는 방식으로 걸리는 시간을 최소화 시키면 된다.

 

도착 시간을 기준으로 오름차순 정렬을 해주면 먼저 도착한 소들의 순서대로 처리를 해줄 수 있으며, 이 경우 매 반복마다 현재까지 걸린 시간 대비 도착한 시간이 빠르면 현재 탐색중인 소의 처리시간만 걸린 시간에 추가해주고, 

만약 도착한 시간이 현재까지 걸린 시간보다 늦다면 현재까지 걸린 시간을 현재 탐색중인 소의 도착 시간 + 현재 탐색중인 소의 처리 시간으로 초기화 해주면 된다.

 

* 코드

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

        Cow[] cowArray = new Cow[count];
        for (int i = 0; i < count; i++) {
            String[] input = br.readLine().split(" ");
            int arrive = Integer.parseInt(input[0]);
            int time = Integer.parseInt(input[1]);

            cowArray[i] = new Cow(arrive, time);
        }

        Arrays.sort(cowArray);
        long result = 0;

        for (int i = 0; i < cowArray.length; i++) {
            if (result >= cowArray[i].arrive) {
                result += cowArray[i].time;
            } else if (result < cowArray[i].arrive) {
                result = cowArray[i].arrive + cowArray[i].time;
            }
        }

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

class Cow implements Comparable<Cow> {
    int arrive;
    int time;

    public Cow(int arrive, int time) {
        this.arrive = arrive;
        this.time = time;
    }

    @Override
    public int compareTo(Cow arg0) {
        if (this.arrive == arg0.arrive) {
            return this.time - arg0.time;
        } else {
            return this.arrive - arg0.arrive;
        }
    }
}

 

매 반복마다 현재 걸린 시간을 기준으로 현재 탐색중인 소의 도착시간이 어떻냐에 따라서만 로직을 수행하고 있다.

전체적인 최적해를 구하는 것이 아닌 매 반복마다 현재 상황을 기준으로 최적의 판단만을 하고 있으므로 그리디 알고리즘 문제에 해당된다.