탐험대 짝꿍 배정
골드 III의견: 0
탐험대에 \(N\)명의 탐험가가 있다. 대장은 탐험가들을 \(N/2\)쌍으로 나눠 짝꿍을 배정하려 한다. 탐험가 \(i\)와 \(j\)를 짝으로 배정할 때 드는 연습 비용은 \(w_{i,j}\)이다 (\(w_{i,j} = w_{j,i}\), \(w_{i,i} = 0\)).
\(N\)명을 빠짐없이, 각자 정확히 한 쌍에 속하도록 짝꿍을 배정할 때 모든 짝의 연습 비용의 합이 최소가 되도록 하여라.
- \(2 \le N \le 16\), \(N\)은 짝수
- \(w_{i,i} = 0\)
- \(i \neq j\)이면 \(1 \le w_{i,j} \le 10\,000\)
- \(w_{i,j} = w_{j,i}\)
첫째 줄에 탐험가의 수 \(N\)이 주어진다. (\(N\)은 짝수이다.)
다음 \(N\)개의 줄 중 \(i\)번째 줄에 \(w_{i,1},\ w_{i,2},\ \ldots,\ w_{i,N}\)이 공백으로 구분되어 주어진다. \(w_{i,i} = 0\)이고 \(i \neq j\)이면 \(1 \le w_{i,j} \le 10\,000\)이다.
모든 짝의 연습 비용의 합의 최솟값을 출력한다.
4
0 1 5 9
1 0 2 5
5 2 0 1
9 5 1 0
2
탐험가 \((1, 2)\)를 짝지으면 비용 \(1\), \((3, 4)\)를 짝지으면 비용 \(1\)로, 총 비용 \(2\)가 최소이다.
6
0 1 10 10 10 10
1 0 10 10 10 10
10 10 0 1 10 10
10 10 1 0 10 10
10 10 10 10 0 1
10 10 10 10 1 0
3
\((1, 2)\), \((3, 4)\), \((5, 6)\) 세 쌍의 비용이 각각 \(1\)이므로 총 비용 \(3\)이 최소이다.
riseoj 작성
출처 Original
평가 및 의견
탐험대 짝꿍 배정
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
탐험대 짝꿍 배정