문제 설명
대리인 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번 생선을 0
3에 다듬고 35에 포장합니다. 1번 생선은 34에 다듬은 뒤 포장 기계가 비는 5까지 기다려 59에 포장하므로 9에 끝납니다. - 1번 생선을 먼저 하면 1번은 0
1에 다듬고 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개도 함께 채점해요.