시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 128 MB | 413 | 208 | 164 | 66.129% |
N명의 학생들에게 N개의 문제가 출제되었다. 학생들은 각자 한 문제씩을 할당받아 그 문제만을 풀려고 한다. 즉, 모든 학생이 서로 다른 문제를 하나씩 맡아서 푸는 것이다.
문제 1 | 문제 2 | 문제 3 | |
---|---|---|---|
학생 1 | 1 | 3 | 3 |
학생 2 | 2 | 3 | 3 |
학생 3 | 3 | 2 | 4 |
모든 학생들은 서로 잘 풀 수 있는 문제가 다르기 때문에, 각 문제마다 문제를 푸는 데 걸리는 시간이 다를 수가 있다. 예를 들어 위의 표처럼 문제 1을 푸는 데 학생 1은 1시간이 걸리지만, 학생2는 2시간이 걸린다.
우리는 모든 학생들이 문제를 푸는 데 걸리는 시간의 총 합을 최소화하고 싶다. 예를 들어 학생 1이 문제 1을 풀고, 학생 2가 문제 3을 풀고, 학생 3이 문제 2를 풀면, 문제를 푸는 데 걸리는 시간의 합은 1 + 3 + 2 = 6이 된다. 문제를 푸는 데 걸리는 시간을 이보다 더 짧게 할 수는 없다.
N명의 학생이 N개의 문제를 푸는 데 걸리는 시간이 모두 주어졌을 때, 각 학생에게 서로 다른 문제를 하나씩 할당하여, 문제를 푸는 데 걸리는 시간의 총 합을 최소화하는 프로그램을 작성하시오.
첫째 줄에는 N(1 ≤ N ≤ 100)이 주어지고, 둘째 줄부터 N개의 줄에 걸쳐 각 학생이 N개의 문제를 푸는 데 걸리는 시간을 나타내는 N개의 정수가 순서대로 주어진다. 주어지는 모든 정수는 1,000을 넘지 않는다.
각 학생에게 서로 다른 문제를 하나씩 할당하여, 문제를 푸는 데 걸리는 시간의 총 합의 최솟값을 출력한다.
3 1 3 3 2 3 3 3 2 4
6