A, B 두 마을의 주민들이 모여서 줄다리 기 시합을 하려고 한다.
줄다리기에 참여 할 사람들은 운동장에 각 동네별로 각각 한 줄씩 늘어서 있다. 우리는 이 줄을 각 각 A줄, B줄이라고 부르기로 한다. 우리는 A줄(B줄)을 A1, A2, A3 (B1, B2, B3) 3개로 잘라 각 A1:B1, A2:B2, 그리 고 A3:B3로 짝을 지어 모두 3번의 줄다리기 시합을 하려고 한다.
우리는 A1, A2, A3, B1, B2, B3 각각을 단위 줄이라 고 부른다. 그리고 단위 줄에 속한 사람 들의 몸무게의 합을 단위 줄의 무게라고 부르기로 한다.
이 문제에서 A, B줄은 각 줄에 늘어선 사람들의 몸무게를 나타내는 정수로 표시 된다.
예를 들어 10명과 8명의 사람으로 구성된 A, B 줄이 다음과 같다고 하자.
A: 62,34,54,26,65,40,30,29,35,32 B: 44,45,66,76,35,60,34,60
우리는 아래와 같이 2개의 ‘|’를 사용하 여 분리된 각 단위 줄을 나타내고자 한다.
A: 62,34,54 | 26,65,40,30 | 29,35,32 B: 44,45,66 | 76,35,60 | 34,60
위의 예에서 단위 줄 A1은 <62,34,54> 이며, 그 무게는 150이다. 그리고 단위 줄 B3은 <34, 60>이며 그 무게는 94가 된다.
그런데 시합을 좀 더 흥미롭게 만 들기 위하여 우리는 반드시 다음의 규칙 을 만족시키고자 한다.
예를 들어 A1을 <62,34>로, B1을 <44,45,66>로 편성하면 이것은 규칙3을 위반하는 것이므로 그러한 단위 줄 편성 은 불가능하다. 대응하는3개 단위 줄 무게의 차이 중, 가장 큰 값을 줄다리기 값이라고 한다면, 우리는 시합을 흥미롭게 진행하기 위하여 가장 작은 줄다리기 값을 가지는 단위 줄 편성을 찾고자 한다.
만일 대응하는 단위 줄의 무게 차이가 각각 10, 15, 12 라고 한다면 이 상황에 서의 줄다리기 값은 15가 된다. 만일 다르게 단위 줄을 편성하여 그 무게 차이가 각각 8, 17, 4 이라고 하면 그 줄다리기 값은 17이 되어 전자가 후자보다 더 나은 편성이 된다.
A, B줄의 몸무게 값을 순서대로 받아서 줄다리기 값을 최소로 하는 단위 줄 편성을 찾아내는 프로그램을 작성하시오.
입력에 따라서 어떤 경우에는 최소의 줄 다리기 값을 가지는 단위 줄 편성이 한 개 이상 존재할 수도 있는데, 그러한 경 우에는 그 중 한 가지만 출력하면 된다.
입력 10 8 62 34 54 26 65 40 30 29 35 32 44 45 66 76 35 60 34 60 출력 3 4 3 3 3 2 입력 7 5 20 20 20 60 40 30 20 61 32 30 71 22 출력 3 1 3 1 2 2
출처: 제26회 한국정보올림피아드 (2009.7.17) 고등부 문제 2 special judge: tamaki