사과 나누기

면접 대비

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

요약

바구니 N개에 담긴 사과 수가 주어질 때, 왼쪽과 오른쪽의 사과 개수 차이가 가장 작아지는 분할 위치를 구합니다.

난이도: 쉬움10점 중 3점
유형: 배열, 누적 합
정답자: 아직 제출이 없습니다

문제

바구니 $N$ 개가 왼쪽에서 오른쪽으로 $1 \ldots N$ 번까지 번호순으로 일렬로 놓여 있다. $i$ 번 바구니에는 사과가 $K_i$ 개 들어 있다. 존과 메리는 두 바구니 사이에 선을 하나 긋는다. 선의 왼쪽에 있는 바구니는 존이, 오른쪽에 있는 바구니는 메리가 모두 가진다. 두 사람이 사과를 최대한 고르게 나눌 수 있도록 선을 긋는 위치를 찾아라.

입력

첫 줄에 바구니 개수 $N$ 이 주어진다 ( $2 \le N \le 1\,000\,000$ ). 이어지는 $N$ 개의 줄에는 각각 정수 $K_i$ 가 한 개씩 주어지며, 이는 $i$ 번 바구니에 들어 있는 사과의 개수이다 ( $1 \le i \le N$ , $0 \le K_i \le 10\,000$ ).

출력

한 줄에 정수 하나를 출력한다. 이 정수는 선을 그었을 때 그 오른쪽에 있는 바구니의 번호이며, 존과 메리가 받는 사과 개수 차이의 절댓값이 가장 작아야 한다. 가능한 답이 여러 개이면 그중 아무거나 하나를 출력한다.

예제1

예제 1
입력
```
7
4
2
10
2
9
3
7
```
예상 출력
```
4
```