{}연습장
대시보드학습스킬 경로문제모의고사라이브 코테복습데이터
문제 목록〉그리디〉배송 부담 최소 배정← 이전다음 →
#081 · 그리디쉬움정렬 + 그리디

배송 부담 최소 배정

문제

오늘 배송할 물품이 n 개, 출근한 배송 기사도 정확히 n 명입니다. weights[i] 는 i 번 물품의 무게이고, fatigue[j] 는 j 번 기사의 피로도 계수입니다.

기사 한 명은 물품을 정확히 한 개씩 맡습니다. 어떤 기사가 어떤 물품을 맡으면 그 조합의 부담은 무게 × 피로도 계수 이고, 하루 전체 부담은 모든 조합의 부담을 더한 값입니다.

배차를 자유롭게 정할 수 있을 때, 하루 전체 부담의 최솟값을 반환하세요.

solution(weights: number[], fatigue: number[]): number

예시

weights fatigue 반환값
[3, 8, 2] [5, 1, 4] 30
[7] [9] 63
[4, 9, 1, 6] [3, 2, 7, 5] 63
[2, 2, 2] [6, 6, 6] 36

첫 번째 예시의 최적 배차는 무게 8인 물품을 피로도 1인 기사에게, 무게 3을 피로도 4인 기사에게, 무게 2를 피로도 5인 기사에게 맡기는 것입니다.

8 × 1 + 3 × 4 + 2 × 5 = 8 + 12 + 10 = 30

제약 조건

  • 1 ≤ weights.length = fatigue.length ≤ 200,000
  • 1 ≤ weights[i] ≤ 10,000
  • 1 ≤ fatigue[j] ≤ 10,000
  • 물품과 기사는 일대일로 모두 배정되어야 합니다

시간 복잡도 목표: O(N log N)

테스트 케이스

예시 1: 무거운 물품에 낮은 피로도
입력: weights = [3,8,2], fatigue = [5,1,4]
출력: 30
예시 2: 물품과 기사가 하나씩
입력: weights = [7], fatigue = [9]
출력: 63
예시 3: 네 건 배차
입력: weights = [4,9,1,6], fatigue = [3,2,7,5]
출력: 63
예시 4: 값이 모두 같아 배차와 무관
입력: weights = [2,2,2], fatigue = [6,6,6]
출력: 36
정순 배정(101)보다 역순 배정이 유리
입력: weights = [10,1], fatigue = [10,1]
출력: 20
중복 값이 섞인 경우
입력: weights = [12,5,5,20], fatigue = [4,4,9,1]
출력: 133
값 편차가 큰 경우
입력: weights = [1,1000,10000], fatigue = [10000,1000,1]
출력: 1020000
같은 무게가 서로 다른 기사에게
입력: weights = [6,6,1], fatigue = [2,9,9]
출력: 75
solution.ts
에디터 로딩 중…

▶ 실행은 기록 없이 채점만, 제출은 결과가 진행률·오답노트에 기록됩니다.