문제
N명의 학생들이 있다. 두 학생 i와 j의 친밀도는 F(i, j)이다.
선생님은 학생들을 두 강의실에 나누려고 한다. 문제는 같은 반에 친한 학생들이 있으면 강의실의 분위기가 시끄럽다는 것이다. 한 강의실의 소란도는 가장 친한 학생들의 친밀도 max(F(i,j))이다.
학생들의 친밀도 정보가 주어지면 두 강의실의 소란도의 합이 최소가 되도록 학생들을 배치하는 프로그램을 작성하여라.
입력
첫 번째 줄에 학생의 수 N (1 ≤ N ≤ 200)이 주어진다. 두 번째 줄부터 N개의 줄에는 친밀도의 정보가 주어진다.
1+i번째 줄에는 N-i개의 수가 들어오며 j번째 수는 학생 i와 학생 i+j의 친밀도 F(i, i+j)를 의미한다. (0 ≤ F(i, i+j) ≤ 1,000,000,000)
출력
학생들을 두 그룹으로 나눴을 때 소란도의 합의 최솟값을 출력한다.
예제 #1
5
4 5 0 2
1 3 7
2 0
4
4
예제 #2
7
1 10 5 5 5 5
5 10 5 5 5
100 100 5 5
10 5 5
98 99
3
15
출처
ACM ICPC World Finals 2014
로그인해야 코드를 작성할 수 있어요.