시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 128 MB | 502 | 147 | 109 | 28.912% |
s(i,k)를 배열 A의 i번째 원소부터 시작하는 연속된 k개 수의 합이라고 정의하자.
s(i,k) = A[i] + A[i+1] + ... + A[i+k-1]
i+k ≤ j일 때, s(i,k) 와 s(j,k)의 차이 (abs(s(i, k) - s(j, k)))를 최소로 하는 프로그램을 작성하시오. 즉, 동일한 길이의 겹치지 않는 두 부분 수열의 차이를 최소로 하는 것이다.
첫째 줄에 n이 주어진다. n은 2보다 크거나 같고, 3,000보다 작거나 같은 자연수이다. 둘째 줄에는 배열 A의 원소가 A[0]부터 차례대로 주어진다. A[i] ≤ 1,000,000,000인 자연수 또는 0이다.
첫째 줄에 값이 가장 작을 때 k를 출력하고, 둘째 줄에 차이의 최솟값을 출력한다. 만약 최솟값이 여러 개일 경우에는 k를 최대로 한다.
5 5 19 11 12 15
2 1
12 8 169 1135 652 1940 1296 1618 1457 491 974 1779 330
5 161