Lv.3bitmaskdp
작업 배정 최소 비용 (작은 입력)
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
N명의 직원과 N개의 작업이 있습니다. cost[i][j]는 i번 직원이 j번 작업을 맡을 때 드는 비용입니다.
모든 직원이 서로 다른 작업을 정확히 하나씩 맡도록 배정할 때, 비용의 합으로 가능한 최솟값을 반환하세요.
입출력 예
| cost | result |
|---|---|
[[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
제한 사항
-
cost.length,cost[i].length -
cost[i][j]
기대 복잡도
- 시간
- 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 |
힌트
힌트
배정 순서를 모두 시도하면 가지()라서 너무 많습니다.
직원을 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]
복잡도 목표
모든 순열을 확인하는 풀이는 효율성 테스트에서 시간 초과가 납니다. 이면 충분합니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 2548 ms | 도출됨 |
| Java 25 | 1000 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 11 | 판정만 |
| performance | 60 | 5 | 판정만 |