Funcia
Lv.4assignment-problemhungarian-algorithmmatching

작업 배정 최소 비용 (큰 입력)

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

직원 N명에게 작업 N개를 하나씩 맡기려고 합니다. 직원 i가 작업 j를 맡으면 비용이 cost[i][j]만큼 듭니다.

모든 직원이 정확히 하나의 작업을 맡고, 모든 작업이 정확히 한 명에게 배정되도록 할 때, 비용 합의 최솟값을 반환하세요.

입출력 예

costresult
[[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

제한 사항

  • 1≤N=1 \le N = cost.length ≤300\le 300, 모든 cost[i].length =N= N
  • 0≤0 \le cost[i][j] ≤1,000,000\le 1{,}000{,}000

기대 복잡도

시간
O(N^3)
공간
O(N)

입출력 예

cost기대 출력
[[4,1,3],[2,0,5],[3,2,2]]5
[[7]]7
[[1,2],[3,6]]5

힌트

힌트

모든 배정을 시도하면 N!N!, 비트마스크 DP도 2N2^N이라 N=300N = 300에서는 불가능합니다. 이 문제는 할당 문제(가중치 이분 매칭)이고, 표준 해법은 헝가리안 알고리즘입니다.

잠재력(potential)과 동치 비용

직원마다 u[i], 작업마다 v[j]를 두고 u[i] + v[j] ≤ cost[i][j]를 항상 지킵니다. 등호가 성립하는 칸(빡빡한 칸)만으로 완전 매칭을 만들 수 있으면, 그 매칭의 비용은 ∑u+∑v\sum u + \sum v이고 이것이 최솟값입니다(어떤 배정도 이보다 쌀 수 없으므로).

직원을 한 명씩 추가

  1. 새 직원에서 시작해 빡빡한 칸과 기존 매칭을 번갈아 따라가는 교대 트리를 키웁니다.
  2. 아직 트리에 없는 작업까지 빡빡한 칸이 없으면, 트리 안 직원·밖 작업 사이의 최소 여유 delta만큼 트리 안 직원의 u를 올리고 트리 안 작업의 v를 내려 새 빡빡한 칸을 만듭니다.
  3. 아직 배정되지 않은 작업에 닿으면 교대 경로를 뒤집어 매칭을 하나 늘립니다.

작업마다 "트리에서 그 작업까지의 최소 여유" minv[j]를 누적 관리하면 직원 한 명당 O(N2)O(N^2), 전체 O(N3)O(N^3)입니다. 매 단계 delta를 처음부터 다시 계산하면 O(N4)O(N^4)이 되어 느립니다.

최소 비용 최대 유량(MCMF)으로도 풀 수 있지만, 상수가 큰 구현은 시간 제한이 빠듯할 수 있습니다.

복잡도 목표

O(N3)O(N^3)이 필요합니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.133226 ms도출됨
Java 251070 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4011판정만
performance605판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.