본문 바로가기

알고리즘

생선 자동 포장 공장

New Era · 12번Lv. 3그리디

생선 자동 포장 공장

문제 설명

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

(주)캣네생선의 생선 공장은 '생선 준비 → 생선 다듬기 → 생선 포장' 순서로 일합니다. 대리인 No.1은 직원들이 버튼만 누르던 일을 자동 포장 프로그램에 맡기고, 직원들은 지식과 마법을 배우러 보냈습니다.

"기계가 노는 시간을 줄이면 모두가 더 일찍 퇴근할 수 있다냥!"

오늘 준비를 마친 생선이 n마리 있습니다. 공장에는 다듬기 기계 1대와 포장 기계 1대가 있고, 생선마다 다듬는 데 걸리는 시간과 포장하는 데 걸리는 시간이 다릅니다. 기계는 아래 규칙으로 움직입니다.

  • 모든 생선은 먼저 다듬기 기계에서 다듬은 뒤, 포장 기계에서 포장합니다.
  • 각 기계는 한 번에 생선 한 마리만 다룹니다. 한 번 시작한 생선은 끝날 때까지 기계에서 빼지 않습니다.
  • 다듬기가 끝난 생선만 포장할 수 있습니다. 다듬기를 끝낸 생선은 포장 기계가 빌 때까지 기다릴 수 있고, 두 기계 사이를 옮기는 시간은 없습니다.
  • 시각 0에 일을 시작합니다. 생선을 기계에 넣는 순서는 마음대로 정할 수 있고, 입력에 적힌 순서를 따를 필요가 없습니다.

생선마다 [다듬기 시간, 포장 시간]이 담긴 목록이 주어질 때, 순서를 잘 정해서 마지막 생선의 포장이 끝나는 시각을 가장 이르게 만들려고 합니다. 그 가장 이른 시각을 반환하는 solution 함수를 작성해 주세요.


제한 사항

  • 1 ≤ 생선 수 n ≤ 10,000
  • data[i] = [i번 생선의 다듬기 시간, i번 생선의 포장 시간]
  • 1 ≤ 다듬기 시간, 포장 시간 ≤ 1,000 (정수)

입출력 예

입력출력
[[3, 2], [1, 4]]7
[[5, 2], [1, 6], [9, 7], [3, 8], [10, 4]]30
[[4, 4], [2, 2], [6, 1]]13

입출력 설명

입출력 예 #1

  • 적힌 순서대로 하면 0번 생선을 03에 다듬고 35에 포장합니다. 1번 생선은 34에 다듬은 뒤 포장 기계가 비는 5까지 기다려 59에 포장하므로 9에 끝납니다.
  • 1번 생선을 먼저 하면 1번은 01에 다듬고 15에 포장, 0번은 14에 다듬고 57에 포장하므로 7에 모두 끝납니다. 이보다 빠를 수는 없으므로 답은 7입니다.

입출력 예 #2

  • 1번 → 3번 → 2번 → 4번 → 0번 순서로 하면 다듬기는 1, 4, 13, 23, 28에 끝나고, 포장은 7, 15, 22, 27, 30에 끝납니다. 30보다 일찍 끝내는 순서는 없습니다.

입출력 예 #3

  • 1번 → 0번 → 2번 순서로 하면 다듬기는 2, 6, 12에 끝나고 포장은 4, 10, 13에 끝납니다. 다듬기 시간의 합이 12라서 마지막으로 다듬는 생선은 빨라야 12에 다듬기가 끝나고, 포장에 1 이상 걸리므로 13보다 빠를 수 없습니다.

예시 테스트

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

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