Funcia
Lv.3bitmaskdp

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

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

N명의 직원과 N개의 작업이 있습니다. cost[i][j]는 i번 직원이 j번 작업을 맡을 때 드는 비용입니다.

모든 직원이 서로 다른 작업을 정확히 하나씩 맡도록 배정할 때, 비용의 합으로 가능한 최솟값을 반환하세요.

입출력 예

costresult
[[9, 2, 7], [6, 4, 3], [5, 8, 1]]9
[[4]]4
[[1, 2], [1, 100]]3

입출력 예 설명

예 1 — 0번 직원에게 1번 작업(2), 1번 직원에게 0번 작업(6), 2번 직원에게 2번 작업(1)을 맡기면 2 + 6 + 1 = 9입니다.

예 3 — 두 직원 모두 0번 작업이 가장 싸지만 한 명만 맡을 수 있습니다. 0번 직원이 1번 작업(2), 1번 직원이 0번 작업(1)을 맡는 3이 최소입니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(cost: int[][]) → int

제한 사항

  • 1≤N=1 \le N = cost.length ≤20\le 20, cost[i].length =N= N
  • 0≤0 \le cost[i][j] ≤106\le 10^6

기대 복잡도

시간
O(N * 2^N)
공간
O(2^N)

입출력 예

cost기대 출력
[[9,2,7],[6,4,3],[5,8,1]]9
[[4]]4
[[1,2],[1,100]]3

힌트

힌트

배정 순서를 모두 시도하면 N!N!가지(20!≈2.4×101820! \approx 2.4 \times 10^{18})라서 너무 많습니다.

직원을 0번부터 차례로 배정한다고 생각하면, 중요한 것은 어떤 작업들이 이미 쓰였는지뿐입니다. 쓰인 작업의 집합을 비트마스크 mask로 나타내면, 지금 배정할 직원은 popcount(mask)번입니다.

dp[0] = 0
for mask in 0 .. 2^N - 1:
    i = popcount(mask)          # 다음에 배정할 직원
    for j not in mask:
        dp[mask | 1<<j] = min(dp[mask | 1<<j], dp[mask] + cost[i][j])
answer = dp[2^N - 1]

복잡도 목표

모든 순열을 확인하는 O(N⋅N!)O(N \cdot N!) 풀이는 효율성 테스트에서 시간 초과가 납니다. O(N⋅2N)O(N \cdot 2^N)이면 충분합니다.

언어별 시간 제한

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

테스트 그룹

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

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