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

문제

N마리의 소가 길을 건너려고 합니다. 소는 한 번에 한 마리씩만 길을 건널 수 있으며, 각 소가 도착한 시간과 길을 건너는 데 걸리는 시간이 주어집니다. 모든 소가 길을 건너는 데 걸리는 최소 시간을 구하는 문제입니다.

• 입력: 첫째 줄에 소의 수 N (1 ≤ N ≤ 100)이 주어집니다. 둘째 줄부터 N개의 줄에 각 소가 도착한 시간과 길을 건너는 데 걸리는 시간이 주어집니다.
• 출력: 모든 소가 길을 건너는 데 걸리는 최소 시간을 출력합니다.

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

풀이

이 문제는 소들이 도착한 순서대로 길을 건너게 하는 것이 가장 효율적입니다. 따라서 도착 시간을 기준으로 오름차순 정렬한 뒤, 소요 시간을 누적해 나가는 그리디 방식을 사용합니다.

1. 객체 생성 및 정렬: 소의 도착 시간(s)과 건너는 데 걸리는 시간(t)을 담을 Cow 클래스를 생성합니다. 배열에 소들의 정보를 입력받은 뒤, Comparator.comparingInt를 사용하여 도착 시간을 기준으로 오름차순 정렬합니다.
2. 시간 누적 시뮬레이션: 현재 시간(ans)을 0으로 초기화하고, 정렬된 소 배열을 순회합니다.
   • 만약 다음 소가 현재 시간(ans)보다 늦게 도착한다면, 소가 올 때까지 기다려야 하므로 시간은 소의 도착 시간(cow.s)으로 건너뜁니다.
   • 만약 다음 소가 현재 시간보다 일찍 도착해서 대기 중이라면, 앞선 소가 끝난 직후(현재 시간 ans)에 바로 길을 건너기 시작합니다.
   • 즉, 소가 길을 건너기 시작하는 시간은 Math.max(ans, cow.s)가 되며, 여기에 소가 건너는 데 걸리는 시간(cow.t)을 더해 현재 시간을 갱신합니다.

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       int n = Integer.parseInt(br.readLine());
       Cow[] cows = new Cow[n];
       for (int i = 0; i < n; i++) {
          StringTokenizer st = new StringTokenizer(br.readLine());
          cows[i] = new Cow(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
       }

       // 도착 시간(s)을 기준으로 오름차순 정렬
       Arrays.sort(cows, Comparator.comparingInt(c -> c.s));

       int ans = 0;
       for (Cow cow : cows) {
          // 현재 시간과 소의 도착 시간 중 더 늦은 시간에 길을 건너기 시작
          ans = Math.max(ans, cow.s) + cow.t;
       }

       bw.write(ans + "");

       bw.flush();
       bw.close();
       br.close();
    }

    static class Cow {
       int s, t;

       Cow(int s, int t) {
          this.s = s;
          this.t = t;
       }
    }
}

알고리즘 분류

정렬 (Sorting), 그리디 알고리즘 (Greedy)