[백준] 14469 소가 길을 건너간 이유 3 (JAVA)

문제 링크:

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

 

 

난이도: 실버 4

 

 

문제:

이웃 농장의 소가 길을 마구잡이로 건너는 것에 진절머리가 난 존은 극단의 결정을 내린다. 농장 둘레에 매우 큰 울타리를 짓는 것이다. 이렇게 하면 근처 농장 출신의 소가 들어올 일이 거의 없다. 이 일로 주변 소들이 분개하였다. 친구네 집에 놀러 갈 수 없을 뿐만 아니라, 매년 참가하던 국제 젖 짜기 올림피아드에도 올해는 참가할 수 없게 되었기 때문이다.

 

이웃 농장의 소 중 존의 농장에 방문할 수 있는 소가 조금 있긴 하지만, 그들도 안심할 수 있는 건 아니다. 존의 농장에 들어가는 문은 하나밖에 없고, 그 문을 통과하려면 감시관의 길고 긴 검문을 받아야 한다. 여러 마리의 소가 한 번에 들어가려고 하면 줄이 그 만큼 길어진다.

 

N마리의 소가 이 농장에 방문하러 왔다. 소가 도착한 시간과 검문받는 데 걸리는 시간은 소마다 다르다. (물론 같을 수도 있다.) 두 소가 동시에 검문을 받을 수는 없다. 예를 들어, 한 소가 5초에 도착했고 7초 동안 검문을 받으면, 8초에 도착한 그 다음 소는 12초까지 줄을 서야 검문을 받을 수 있다.

 

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

 

 

입력:

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

 

 

출력:

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

 

 

문제 이해:

문제 이해는 어렵지 않다. 첫 줄에는 소의 개수가 주어진다. 이후 줄부터는 각 소의 도착 시간과 검문 시간이 주어진다.

 

 예제 입력 1의 예를 들면, 첫 번째 줄의 숫자 3은 소가 세 마리라는 뜻이다. 다음 줄의 2 1은 한 마리의 소가 2초에 도착해서 검문을 받는 데 1초가 걸린다는 의미다.

 

이제 예제 입력 1의 결과가 왜 15초인지 살펴보자.

 

가장 먼저 도착하는 소는 2초에 도착한다. 따라서 0초부터 2초까지 시간은 그냥 흐른다. 2초가 되면 첫 번째 소가 검문을 시작하고, 1초가 걸리므로 3초에 검문을 마친다.

 

다음으로 도착하는 소는 5초에 온다. 3초부터 5초까지는 대기 시간이 흐르고, 5초가 되면 세 번째 소가 도착해 7초 동안 검문을 받는다. 따라서 12초에 검문이 끝난다.

 

이 과정에서 두 번째 소는 8초에 도착하지만, 그때는 이미 검문이 진행 중이므로 기다려야 한다. 12초가 되어야 검문을 시작할 수 있고, 3초가 걸리므로 최종적으로 15초에 모든 검문이 완료된다.

 

 

구현 방향:

이 문제를 보았을 때, 최근에 우선순위 큐를 자주 다뤘던 터라 자연스럽게 우선순위 큐(PriorityQueue)가 떠올랐다.

 

소의 도착 시간과 검문 시간을 각각 하나의 원소로 묶어 큐에 넣고,
도착 시간을 기준으로 우선순위를 설정하면 큐에서 꺼낼 때마다
항상 가장 먼저 도착한 소부터 처리할 수 있다.

 

현재 시간이 어떤 소의 도착 시간보다 작다면,
그 소가 도착할 때까지 시간을 흘려보내고,

도착 시간이 현재 시간과 같아졌다면 그때부터 검문 시간만큼
시간을 더해주면 된다.

이 과정을 큐가 빌 때까지 반복하면
모든 소가 검문을 마친 시점을 구할 수 있다.

 

이를 그대로 코드로 구현하면 다음과 같다.

 

 

정답 코드:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static PriorityQueue<int[]> q = new PriorityQueue<>(
            Comparator.comparingInt(a -> a[0])
    );

    public static int solve(){
        //처음 검문하는 시간까지는 빠르게 pass
        int[] peek = q.peek();
        int result= peek[0];


        while (!q.isEmpty()){
            int[] arr = q.poll();
            int arrive=arr[0];
            int check= arr[1];

            //아직 검문 시간에 도달하지 못했을 때
            if (result < arrive) {
                result = arrive;
            }

            // 검문 진행
            result += check;

        }
        return result;

    }

    public static void main(String[] args) throws IOException {
        //초기 세팅
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        N=Integer.parseInt(br.readLine());

        for(int i=0; i<N; i++){
            StringTokenizer st=new StringTokenizer(br.readLine());
            int arrive=Integer.parseInt(st.nextToken());
            int check= Integer.parseInt(st.nextToken());
            q.add(new int[]{arrive,check}); // 도착시간 검문시간 Push
        }
        //초기 세팅 끝

        //탐색 시작
        int result = solve();

        //결과 출력
        System.out.println(result);
    }
}

 

 

마무리하며:

최근에는 주로 골드 난이도의 문제들을 풀어왔기 때문에, 이번 문제는 비교적 난이도가 낮게 느껴져 빠르게 해결할 수 있었다.
짧은 시간 안에 문제를 이해하고 구현까지 마칠 수 있었던 것은, 꾸준히 코딩 테스트 문제를 풀며 쌓아온 경험 덕분인 것 같다.

 

 

감사합니다.