균형 잡힌 팀

면접 대비

시간 제한1초메모리 제한128 MB

요약
실력값이 주어진 소 12마리를 3마리씩 4팀으로 나누어 팀 실력 합이 가장 큰 팀과 가장 작은 팀의 차이를 최소화합니다.
난이도

보통10점 중 4점

유형
완전 탐색, 백트래킹
정답자
아직 제출이 없습니다

문제

농부 존의 소 12마리가 올해 겨울 무림픽에 출전한다. 각 소의 능력치는 1 이상 1,000,000 이하의 정수다.

존은 소를 3마리씩 네 팀으로 나누려고 한다. 팀의 능력치는 그 팀에 속한 소 세 마리의 능력치를 모두 더한 값이다. 존은 네 팀의 실력이 최대한 고르기를 바란다. 즉 네 팀의 능력치 중 최댓값 SS와 최솟값 ss의 차이 S−sS - s를 가장 작게 만들고 싶다.

S−sS - s의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄부터 열두째 줄까지 각 줄에 소 한 마리의 능력치가 주어진다. 능력치는 1 이상 1,000,000 이하의 정수다.

출력

첫째 줄에 S−sS - s의 최솟값을 출력한다.

힌트

능력치가 1부터 12까지 하나씩 주어진 경우를 보자. 팀을 (12, 1, 7), (9, 8, 3), (10, 5, 4), (11, 2, 6)으로 나누면 앞의 두 팀은 능력치가 20이고 뒤의 두 팀은 19다. 이때 S−sS - s는 1이며, 이보다 작게 만드는 방법은 없다.

예제1

  1. 예제 1

    입력
    1
2
3
4
5
6
7
8
9
10
11
12
    예상 출력
    1