문제
물양갱은 팥소를 틀에 넣고 한천으로 굳혀 만드는 과자이다. JOI 군 앞에는 가로로 긴 직육면체 모양의 물양갱이 하나 있다. 오늘 간식으로 이 물양갱을 먹기로 했다. 물양갱에는 세로 방향 칼집이 모두 \(N-1\)곳에 나 있다. 물양갱의 길이는 \(L_1 + L_2 + \cdots + L_N\)이고, \(i\)번째 (\(1 \le i \le N-1\)) 칼집은 왼쪽에서 \(L_1 + L_2 + \cdots + L_i\)인 위치에 있다. 통째로 먹기에는 너무 커서, JOI 군은 칼집 가운데 \(1\)곳 이상을 골라 그 칼집을 따라 잘라 여러 조각으로 나누기로 했다. 조각 크기가 들쭉날쭉하면 보기가 좋지 않으므로, 가장 긴 조각과 가장 짧은 조각의 길이 차가 되도록 작아지도록 자른다. 가장 긴 조각과 가장 짧은 조각의 길이 차의 최솟값을 구하는 프로그램을 작성하라. |
입력
입력은 다음 형식으로 주어진다.
\(N\)
\(L_1\)
\(L_2\)
\(\vdots\)
\(L_N\)
- 첫째 줄에 정수 \(N\)이 주어진다.
- 다음 \(N\)줄의 \(i\)번째 줄에 정수 \(L_i\)가 주어진다.
- \(2 \le N \le 50\)
- \(1 \le L_i \le 1000\)
- 입력되는 값은 모두 정수이다.
출력
다음 형식으로 출력한다.
첫째 줄에 가장 긴 조각과 가장 짧은 조각의 길이 차의 최솟값을 출력한다.
예시 1
입력
11
2
3
8
4
7
6
6
5
1
7
5
출력
2
설명
\(4\)번째와 \(7\)번째 칼집을 따라 자르면 길이가 \(17\), \(19\), \(18\)인 세 조각이 된다. 가장 긴 조각은 \(19\), 가장 짧은 조각은 \(17\)이므로 차는 \(2\)이다. 이것이 최솟값이므로 \(2\)를 출력한다.
예시 2
입력
2
1
10
출력
9
설명
크기가 아무리 들쭉날쭉해도 반드시 \(1\)곳 이상은 잘라야 한다.
예시 3
입력
5
5
5
5
5
5
출력
0
설명
이 예에서는 물양갱을 같은 크기의 \(5\)조각으로 나눌 수 있다.