문제
N개의 정수로 구성된 배열 arr[]이 오름차순으로 정렬되어 주어진다.
이 배열에서 적어도 1개의 원소를 포함하는
임의의 연속된 구간의 합이 0에 가장 가까운 구간을 찾는 프로그램을 작성해보자.
예를 들어 N이 7인 배열 arr[]이 아래와 같다고 하자.
-10, -5, -3, 2, 7, 9, 13
이 경우 -10, -5, -3, 2, 7, 9 구간의 합을 구하면 0이 되므로 0에 가장 가까운 구간이다.
입력
첫 행에 N이 입력된다. ( 1 <= N <= 100,000)
다음 행에 N개의 정수 arr[i]가 공백으로 구분되어 입력된다.
( -1,000,000 <= arr[i] <= 1,000,000)
[제약사항]
* 전체 데이터에서 20% 에 해당하는 데이터는 1 <= N <= 1000 이다.
* 전체 데이터에서 20% 에 해당하는 데이터는 1,000 < N <= 10,000 이다.
* 전체 데이터에서 60% 에 해당하는 데이터는 10,000 < N <= 100,000 이다.
출력
첫 행에 합이 0에 가장 가까운 구간의 합을 출력한다.
다음 행에 구간의 시작 인덱스 s와 끝 인덱스 e를 공백으로 구분하여 출력한다.
인덱스는 1 ~ N까지 이고 s <= e 이다.
답이 되는 구간이 여러 개인 경우 인덱스 s가 작은 것을 출력한다.
그래도 같은 경우 어느것을 출력하든 정답으로 간주된다.
예제 #1
7
-10 -5 -3 2 7 9 13
0
1 6
예제 #2
5
1 2 3 4 5
1
1 1
예제 #3
3
-5 -4 8
-1
1 3
출처
comkiwer
로그인해야 코드를 작성할 수 있어요.