본문 바로가기

알고리즘

자바독의 저녁 대접

New Era · 14번Lv. 3시뮬레이션

자바독의 저녁 대접

문제 설명

대리인 No.1의 기록 중에서

오늘 자바독에게서 편지가 왔다. 라이언에게 끌려가 SI 작업에 시달리던 특급 기술자들을 고향으로 불러, 매일 저녁 직접 요리를 대접하고 있다고 한다. 손님을 오래 기다리게 하지 않는 순서를 묻기에, 우리 회사의 프로그램으로 계산해 주기로 했다냥.

자바독의 부엌에는 화구가 k개 있고, 손님 n명이 저녁을 먹으러 옵니다. 손님마다 도착 시각과, 그 손님의 요리를 만드는 데 걸리는 시간이 정해져 있습니다. 자바독은 아래 규칙으로 요리합니다.

  • 화구 하나에서는 한 번에 손님 한 명의 요리만 만듭니다. 시작한 요리는 끝날 때까지 그 화구를 씁니다.
  • 어떤 시각에 빈 화구가 있고 도착해서 기다리는 손님이 있으면, 바로 그 시각에 요리를 시작합니다. 화구를 일부러 비워 두지 않습니다.
  • 기다리는 손님이 여러 명이면 요리 시간이 가장 짧은 손님부터 요리합니다. 요리 시간이 같으면 먼저 도착한 손님, 그것도 같으면 목록에서 앞에 있는 손님부터 합니다.
  • 같은 시각에 요리가 끝나 화구가 비는 일과 손님이 도착하는 일이 함께 일어나면, 그 시각에 도착한 손님도 기다리는 손님으로 함께 고릅니다.
  • 손님의 대기 시간은 (요리를 시작한 시각 − 도착 시각)입니다. 요리하는 시간은 대기 시간에 넣지 않습니다.

화구 수 k와 손님 목록이 주어질 때, 위 규칙대로 요리했을 때 모든 손님의 대기 시간의 합을 반환하는 solution 함수를 작성해 주세요.


제한 사항

  • data는 [k, 손님 목록] 형태입니다.
  • 1 ≤ k ≤ 100
  • 1 ≤ 손님 수 n ≤ 10,000
  • 손님 목록의 i번째 원소는 [i번 손님의 도착 시각, i번 손님의 요리 시간]입니다.
  • 0 ≤ 도착 시각 ≤ 1,000,000, 1 ≤ 요리 시간 ≤ 1,000 (정수)
  • 손님 목록은 도착 시각 순서로 정렬되어 있지 않을 수 있습니다.

입출력 예

입력출력
[3, [[0, 5], [0, 3], [1, 4], [2, 2], [2, 6], [3, 1], [4, 3], [6, 2]]]6
[1, [[0, 4], [1, 3], [2, 1], [3, 2]]]10
[2, [[5, 3], [0, 2], [1, 9], [1, 2], [3, 4], [8, 1]]]5

입출력 설명

입출력 예 #1 (화구 3개, 손님 0번~7번)

시각일어난 일대기 시간
00번·1번 도착, 바로 요리 시작(1번은 3에, 0번은 5에 끝남)0, 0
12번 도착, 남은 화구에서 바로 시작(5에 끝남)0
23번(요리 2)·4번(요리 6) 도착, 빈 화구가 없어 기다림
31번 요리가 끝남. 5번(요리 1) 도착. 기다리는 3번·4번·5번 중 가장 짧은 5번 시작0
45번 요리가 끝남. 6번(요리 3) 도착. 3번·4번·6번 중 가장 짧은 3번 시작3번: 2
50번·2번 요리가 끝나 화구 2개가 빔. 6번, 4번 순서로 시작6번: 1, 4번: 3
63번 요리가 끝남. 7번 도착, 바로 시작0

대기 시간의 합은 2 + 1 + 3 = 6입니다.

입출력 예 #2

  • 화구가 1개입니다. 0번 요리가 4에 끝나면 1번(요리 3)·2번(요리 1)·3번(요리 2)이 기다리고 있습니다.
  • 2번이 4에 시작(대기 2), 3번이 5에 시작(대기 2), 1번이 7에 시작(대기 6)하므로 합은 10입니다.

입출력 예 #3

  • 1에 2번(요리 9)과 3번(요리 2)이 함께 도착하지만 빈 화구는 1개뿐이라 더 짧은 3번이 먼저 시작합니다. 2번은 2에 시작합니다(대기 1).
  • 0번은 5에 도착하지만 두 화구가 모두 바빠서 7에 시작하고(대기 2), 5번은 8에 도착해 10에 시작합니다(대기 2). 합은 1 + 2 + 2 = 5입니다.

예시 테스트

#입력기대값
1[3, [[0, 5], [0, 3], [1, 4], [2, 2], [2, 6], [3, 1], [4, 3], [6, 2]]]6
2[1, [[0, 4], [1, 3], [2, 1], [3, 2]]]10
3[2, [[5, 3], [0, 2], [1, 9], [1, 2], [3, 4], [8, 1]]]5

입력은 solution에 넘기는 인자예요. 제출하면 숨김 테스트 13개도 함께 채점해요.