백준 14469 - 소가 길을 건너간 이유3

문제

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

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

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

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

접근

결국 모든 소가 들어간 시간을 출력한다고 이해했다.

시간을 비교하자!

  • 도착시간에 검문이 진행중이지 않다면 현재 시간을 도착시간으로 변경
  • 이미 검문이 진행중이라면, 검문이 끝나는 대로 다음 검문이 진행될 것이라 생각하고 검문 시간만을 더함
  • 출력

이전에, 소들이 순서대로 올 수 있도록 도착 시간을 기준으로 정렬을 해준다!

코드

Node.js

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const N = parseInt(input[0]);

const tmpCows = input.slice(1);
const infos = [];
for (let cow of tmpCows) {
  const info = cow.split(" ").map(Number);
  infos.push(info);
}

infos.sort((o1, o2) => o1[0] - o2[0]);

let curTime = 0;
for (let info of infos) {
  if (info[0] > curTime) {
    curTime = info[0];
    curTime += info[1];
  } else {
    curTime += info[1];
  }
}

console.log(curTime);

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;


public class Main {
  public static void main(String[] args) throws IOException{
    final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int N = Integer.parseInt(st.nextToken());

    Info[] infos = new Info[N];

    for (int i = 0; i < N; i++ ) {
      st = new StringTokenizer(br.readLine());

      int arrival = Integer.parseInt(st.nextToken());
      int check = Integer.parseInt(st.nextToken());

      infos[i] = new Info(arrival, check);
    }

    Arrays.sort(infos, (o1, o2) -> {
      return o1.arrival - o2.arrival; // Arrival에 맞춰 오름차순 정렬
    });

    int curTime = 0;
    for (Info info : infos ) {
      if (info.arrival > curTime) {
        curTime = info.arrival; // 도착시간으로 바로 설정
        curTime += info.check; // 검문까지 바로
      } else {
        curTime += info.check;
      }
    }
  System.out.println(curTime);
  br.close();
  }

  static class Info {
    int arrival;
    int check;

    public Info (int arrival, int check) {
      this.arrival = arrival;
      this.check = check;

    }
  }
}

결론

왜 소가 이렇게 수상하지?

크게 돌아가지 않고 도착 시간과, 검문에 걸리는 부분을 종이에 그려가며 쉽게 풀 수 있었다.

자바로 먼저 풀고, 노드로 다시 풀어보니 이번에는 또이또이한 문제인 것 같다.

Max를 쓰면 더 깔끔할 것 같다.