2002년 가을학기 문제해결기법 - 문제 9

줄다리기

필승대학교 전산학과는 가을맞이 체육대회를 계획하고 있다. 체육대회의 마지막 행사로 줄다리기를 하기로 하고, 과의 단합과 흥미를 위해서 줄다리기를 하는 양팀의 전력이 비슷하게 되도록 두 팀으로 나누기로 하였다. 각 팀에 속한 학생들의 몸무게 합을 그 팀의 전력이라고 할 때, 두 팀의 전력 차이가 최소가 되도록 N명의 학생을 두 팀으로 나누는 프로그램을 작성하시오.

프로그램 이름과 설명 파일 이름은 각각 tug.xxx, tug.yyy라고 하고 실행 파일 이름은 tug.exe로 한다. 프로그램의 실행 시간은 5초를 초과할 수 없다.

입력 형식

입력 파일의 이름은 INPUT.TXT이다. 첫 줄에는 정수 N (4 ≤N ≤30)이, 둘째 줄에는 각 학생들의 몸무게가 정수로 주어진다. 각 학생들의 몸무게는 45 이상 160 이하이다. 입력되는 정수들 사이에는 공백이 있다.

출력 형식

출력 파일의 이름은 OUTPUT.TXT이다. 전체 N 명의 학생을 각 팀의 전력의 차가 최소가 되도록 두 팀으로 나눌 때의 전력차를 첫째 줄에 출력한다. 그리고 둘째 줄과 셋째 줄에 각 팀에 속한 학생의 몸무게를 오름차순으로 출력한다.

입력과 출력의 예 (1)

INPUT.TXT

4

51 74 52 73

OUTPUT.TXT

0

51 74

52 73

입력과 출력의 예 (2)

INPUT.TXT

4

45 160 45 50

OUTPUT.TXT

20

45 45 50

160