https://www.acmicpc.net/problem/1311
문제 요약
- n개의 사람과 작업이 있음(n = 20)
- 각각의 연결마다 비용이 있음
- 1:1로 매칭이 되어야함
- 최소 비용 구하기
접근법
- n = 20이라 비트마스킹을 하면 될 것 같음
- 일단 완전 탐색을 생각해보면 사람을 순열로 나열한 후 앞에서부터 첫번째 작업을 매핑하는 방법을 생각해볼 수 있음 -> 20!개
- 앞 사람들이 (1, 2, 3)이든 (3, 2, 1)이든 (2, 1, 3) 이든.... 어쨌든 앞에 작업 3개와 연결을 했을 것임
- 더 확장하면 k 명의 사람이 어떻게 나열이 되었든 앞의 k개의 작업과는 연결을 했을 것임. 그리고 이렇게 연결했을때 최소 비용이 존재 할 것임
- 더 확장하면 [k명의 사람이 앞에서부터 k개의 작업과 연결] 했을때의 최소값을 구할 수 있고 그 다음 값을 구할 수 있음
- dp[1, 5, 4] : 1, 5, 4의 사람이 1, 2, 3 작업과 연결했을때의 최소값
- dp[1, 5, 4, 2] : dp[1, 5, 4] + 2번사람과 4번 작업 연결
- dp[1, 5, 4, 3] : dp[1, 5, 4] + 3번사람과 4번 작업 연결
- 중요한 것은 [1, 4, 3] + [5] 로도 [1, 5, 4, 3]이 나올 수 있기 때문에 최소값을 갖고 있어야함
- 반복...
- dp[1, 5, 4]를 하나의 상태로 둘 수 있고, 비트로 표현할 수 있음
- 결국 구하려고 하는 값은 dp[1, 2, 3, ... n]의 값
- dp[X] : X로 표현되는 사람들이 1번 작업부터 할당되었을때의 최소값
- dp[X] =
- Y : X에서 비트하나 제거(= 어떤 사람)
- k : 제거한 사람
- work(k) : 제거한 사람이 그 다음 작업을 할때의 비용
추가
- 헝가리안 알고리즘이라는 것이 있다고 함 : https://en.wikipedia.org/wiki/Hungarian_algorithm
newbieski