드론 측량 임무 배정
골드 II의견: 0
측량 회사는 \(N\) 명의 드론 조종사와 \(N\) 개의 측량 임무를 가지고 있습니다. 조종사 \(i\) 가 임무 \(j\) 를 수행하는 데 드는 비용이 \(C_{i,j}\) 로 주어집니다.
각 조종사는 정확히 하나의 임무를, 각 임무는 정확히 한 조종사가 맡도록 일대일로 배정해야 합니다.
이때 총 비용의 최솟값을 구하세요.
\(1 \le N \le 15\), \(0 \le C_{i,j} \le 1000\)
첫 줄에 정수 \(N\) 이 주어집니다. (\(1 \le N \le 15\))
이어 \(N\) 개의 줄에 각각 \(N\) 개의 정수가 주어지며, \(i\) 번째 줄의 \(j\) 번째 수가 \(C_{i,j}\) 입니다. (\(0 \le C_{i,j} \le 1000\))
모든 조종사를 임무에 일대일 배정했을 때의 최소 총 비용을 출력합니다.
3
9 2 7
6 4 3
5 8 1
9작업자 1→일2(2), 작업자 2→일1(6), 작업자 3→일3(1) 로 배정하면 총 비용 9 로 최소입니다.
2
1 100
100 1
21→1, 2→2 로 배정하면 비용 2 가 최소입니다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
드론 측량 임무 배정
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
드론 측량 임무 배정