작업 할당

프로그램 명: job_assignment

제한시간: 1 초

A,B,C,D 네 사람이 각각 국어,영어,수학, 과학 네 과목 중 하나씩을 서로에게 가르쳐 주고자 한다.

각자가 자신있는 과목을 가르쳐야 능률이 오르기 때문에 이 들은 가장 효과적인 방법을 찾고 자 한다.

국 영 수 과

A 12 37 23 15

B 28 11 21 19

C 24 14 41 40

D 21 23 31 23

이 문제에서는 각 사람이 맡는 과목의 성적의 합이 최대가 되도록 하는 것을 가장 효과적인 방법이라고 생각한다. A,B,C,D 의 각 성적이 위의 표와 같을 때에 표시된 총합은 136 이다.

N 명의 사람의 각 N 과목의 성적표가 주어 졌을 때, 각자가 맡는 과목의 성적의 합이 최대가 되도록 하는 프로그램을 작성하라.

사람과 과목의 수(30 이하)와 각 자의 성적(항상 양의 정수)이 주어진다.

각자가 맡은 과목과 최대가 되는 성적의 합을 출력한다.

입력 

4
12 37 23 15 
28 11 21 19 
24 14 41 40
21 23 31 23

출력 

136
2 1 4 3

출처: www.koi4u.net