작업 배정 최소 비용 (큰 입력)
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
직원 N명에게 작업 N개를 하나씩 맡기려고 합니다. 직원 i가 작업 j를 맡으면 비용이 cost[i][j]만큼 듭니다.
모든 직원이 정확히 하나의 작업을 맡고, 모든 작업이 정확히 한 명에게 배정되도록 할 때, 비용 합의 최솟값을 반환하세요.
입출력 예
| cost | result |
|---|---|
[[4, 1, 3], [2, 0, 5], [3, 2, 2]] | 5 |
[[7]] | 7 |
[[1, 2], [3, 6]] | 5 |
입출력 예 설명
예 1 — 직원 0에게 작업 1(비용 1), 직원 1에게 작업 0(비용 2), 직원 2에게 작업 2(비용 2)를 맡기면 5입니다. 가장 싼 칸 cost[1][1] = 0을 고르면 나머지를 아무리 잘 골라도 6 이상이 됩니다.
예 2 — 직원과 작업이 하나씩뿐입니다.
예 3 — 가장 싼 cost[0][0] = 1을 먼저 고르면 1 + 6 = 7이지만, 2 + 3 = 5가 더 쌉니다. 탐욕적으로 고르면 틀립니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(cost: int[][]) → int
제한 사항
-
cost.length, 모든cost[i].length -
cost[i][j]
기대 복잡도
- 시간
- O(N^3)
- 공간
- O(N)
입출력 예
| cost | 기대 출력 |
|---|---|
[[4,1,3],[2,0,5],[3,2,2]] | 5 |
[[7]] | 7 |
[[1,2],[3,6]] | 5 |
힌트
힌트
모든 배정을 시도하면 , 비트마스크 DP도 이라 에서는 불가능합니다. 이 문제는 할당 문제(가중치 이분 매칭)이고, 표준 해법은 헝가리안 알고리즘입니다.
잠재력(potential)과 동치 비용
직원마다 u[i], 작업마다 v[j]를 두고 u[i] + v[j] ≤ cost[i][j]를 항상 지킵니다. 등호가 성립하는 칸(빡빡한 칸)만으로 완전 매칭을 만들 수 있으면, 그 매칭의 비용은 이고 이것이 최솟값입니다(어떤 배정도 이보다 쌀 수 없으므로).
직원을 한 명씩 추가
- 새 직원에서 시작해 빡빡한 칸과 기존 매칭을 번갈아 따라가는 교대 트리를 키웁니다.
- 아직 트리에 없는 작업까지 빡빡한 칸이 없으면, 트리 안 직원·밖 작업 사이의 최소 여유
delta만큼 트리 안 직원의u를 올리고 트리 안 작업의v를 내려 새 빡빡한 칸을 만듭니다. - 아직 배정되지 않은 작업에 닿으면 교대 경로를 뒤집어 매칭을 하나 늘립니다.
작업마다 "트리에서 그 작업까지의 최소 여유" minv[j]를 누적 관리하면 직원 한 명당 , 전체 입니다. 매 단계 delta를 처음부터 다시 계산하면 이 되어 느립니다.
최소 비용 최대 유량(MCMF)으로도 풀 수 있지만, 상수가 큰 구현은 시간 제한이 빠듯할 수 있습니다.
복잡도 목표
이 필요합니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 3226 ms | 도출됨 |
| Java 25 | 1070 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 11 | 판정만 |
| performance | 60 | 5 | 판정만 |