일 배정하기 1
시간 제한1초메모리 제한512 MB
N by N 비용 행렬이 주어질 때 각 사람에게 작업을 하나씩 배정해 총 비용을 최소화하는 문제입니다.
문제
N명의 사람과 N개의 일이 있습니다. 각 사람은 정확히 하나의 일을 맡아야 하며, 각 일도 정확히 한 사람에게만 배정되어야 합니다. 모든 사람은 모든 일을 할 수 있습니다.
사람과 일에는 각각 1번부터 N번까지 번호가 붙어 있습니다. D_{ij}를 i번 사람이 j번 일을 할 때 드는 비용이라고 할 때, N개의 일을 모두 배정하는 데 필요한 총비용의 최솟값을 구하세요.
입력
첫째 줄에 사람과 일의 수 N (1 <= N <= 20)이 주어집니다. 다음 N개의 줄에는 비용 행렬 D가 주어집니다. 각 줄에는 N개의 자연수 비용이 있으며, 모든 비용은 10,000 이하입니다.
출력
모든 일을 배정하는 데 필요한 총비용의 최솟값을 출력합니다.