보석 가공 장인 배정
골드 II의견: 0
보석 가공 공방에 \(N\) 명의 장인과 \(N\) 개의 원석이 있습니다. 장인 \(i\) 가 원석 \(j\) 를 가공하면 가치 \(C_{ij}\) 의 보석이 만들어집니다. 각 장인은 정확히 하나의 원석을, 각 원석은 정확히 한 명의 장인에게 배정되어야 합니다.
만들어지는 보석들의 가치 합을 최대로 하는 배정을 찾아 그 최대 합을 구하세요.
\(N \le 16\) 이므로 "이미 배정된 원석 집합"을 비트마스크로 나타내는 DP (\(O(2^N \cdot N)\)) 로 풀 수 있습니다. (배정된 원석 수가 곧 현재 장인의 번호입니다.)
- \(1 \le N \le 16\)
- \(0 \le C_{ij} \le 10000\)
첫 줄에 \(N\) 이 주어집니다.
이어서 \(N\) 개의 줄에 걸쳐 가치 행렬 \(C\) 가 주어집니다. \(i\) 번째 줄의 \(j\) 번째 수가 \(C_{ij}\) 입니다.
가능한 최대 가치 합을 한 줄에 출력합니다.
3
3 5 1
2 9 4
8 2 618장인 0→보석 1, 장인 1→보석 2, 장인 2→보석 0 으로 배정하면 \(5+4+8=17\) 로 최대입니다.
2
1 2
3 450→1, 1→0 으로 배정하면 \(2+3=5\) 가 최댓값입니다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
보석 가공 장인 배정
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
보석 가공 장인 배정