Informatica Online Judge

  빼빼로 [2152 / 0868]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 4   Total Tried : 6


The Champion of this Problem (C++) : icp1481 - 0ms / 1164byte
My Best Submission (C++) : N/A

[JOI 2018 예선]

Background

경곽이의 손에는 길쭉한 빼빼로를 가지고 있다.

경곽이는 오늘 간식으로 이 빼빼로를 먹을 예정이다.

이 빼빼로는 독특하게도 세로로 $N-1$개의 절취선이 있으며 각 절취선 사이의 길이는 $L_1$ + $L_2$ + ... + $L_N$이다.

$i$번째 절취선은 $L_1$ + $L_2$ + ... + $L_i$ 번째에 위치한다.

이 빼빼로는 한 번에 먹기에는 너무 길기 때문에 절취선을 한 곳 이상 골라서 잘라 여러 개의 조각으로 나눠 먹기로 했다.

단, 조각의 길이가 서로 너무 차이가 나면 보기 싫으므로 조각들의 최대길이와 최소길이의 차이를 가능한 한 적게하고자 한다.

길이의 최대와 최소의 차의 최솟값을 구하는 프로그램을 작성하시오.

Input

입력형식은 다음과 같다.

$N$
$L_1$
$L_2$
:
$L_N$

[입력값의 정의역]
$2 ≦ N ≦ 50$
$1 ≦ L_i ≦ 1000$ ($1 ≦ i ≦ N$)

Output

길이의 최대와 최소의 차의 최솟값을 출력한다.

IO Example

입력
11
2
3
8
4
7
6
6
5
1
7
5

출력
2

* 설명

(2 3 8 4) (7 6 6) (5 1 7 5)

와 같이 3등분으로 나누면

17, 19, 18

로 최소인 2가 된다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]