합이 0에 가장 가까운 구간 찾기2 > 문제은행



문제은행

3341 : 합이 0에 가장 가까운 구간 찾기2

제한시간: 1000 ms    메모리제한: 256 MB
해결횟수: 23 회    시도횟수: 164 회   



N개의 정수로 구성된 배열 arr[]이 주어진다.

이 배열에서 적어도 1개의 원소를 포함하는 

임의의 연속된 구간의 합이 0에 가장 가까운 구간을 찾는 프로그램을 작성해보자.

 

예를 들어 N이 7인 arr[]이 아래와 같다고 하자.

13, -3, 2, 7, -10, -5, 9

이 경우 -3, 2, 7, -10, -5, 9​ 구간의 합을 구하면 0이 되므로 0에 가장 가까운 구간이다.

 

 ​ 




첫 행에 N이 입력된다. ( 1 <= N <= 300,000)
다음 행에 N개의 정수 arr[i]가 공백으로 구분되어 입력된다. ( -1,000,000,000 <= arr[i] <= 1,000,000,000)

[제약사항]
* 전체 데이터에서 20% 에 해당하는 데이터는 1 <= N <= 5,000 이다.
* 전체 데이터에서 20% 에 해당하는 데이터는 5,000 < N <= 50,000 이다.
* 전체 데이터에서 60% 에 해당하는 데이터는 50,000 < N <= 300,000 이다.



첫 행에 합이 0에 가장 가까운 구간의 합을 출력한다.
다음 행에 구간의 시작 인덱스와 끝 인덱스를 공백으로 구분하여 출력한다. 
인덱스는 1 ~ N까지이다.
답이 되는 구간이 여러 개인 경우 시작 인덱스가 작은 것을 출력한다.
그래도 같은 경우 끝 인덱스가 작은 것을 출력한다.


7
13 -3 2 7 -10 -5 9
0
2 7


5
4 5 1 2 3
1
3 3


3
-4 -5 8
-1
1 3


출처 : comkiwer




HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 031-388-0999 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.