7156 : 두 배열 최적 매칭
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
N명의 학생과 N개의 과제가 있습니다. 각 학생이 각 과제를 수행할 때 발생하는 비용이 N×N 행렬로 주어집니다. 모든 학생에게 서로 다른 과제를 하나씩 배분할 때 발생하는 최소 비용의 합을 출력하십시오.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 학생과 과제의 수 N이 주어집니다. (1 ≤ N ≤ 8)
둘째 줄부터 N개의 줄에 걸쳐 학생의 과제별 비용 행렬(N×N)이 공백으로 구분되어 주어집니다. (비용 ≤ 1,000)
둘째 줄부터 N개의 줄에 걸쳐 학생의 과제별 비용 행렬(N×N)이 공백으로 구분되어 주어집니다. (비용 ≤ 1,000)
출력 설명
과제 배분의 최소 비용 합을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3
1 2 3
4 5 6
7 8 9
출력 예시
COPY
복사되었습니다!
복사되었습니다!
15도움
1번 학생-1과제(1), 2번 학생-2과제(5), 3번 학생-3과제(9)는 합이 15입니다. 최소 비용을 구하는 배정은 1-3(3), 2-2(5), 3-1(7) 등도 합이 15입니다. (실제 최소 비용은 1-3(3) + 2-1(4) + 3-2(8) = 15 등)