[Gold IV] 부분합 - 1806 (누적합, 투포인터)

[Gold IV] 부분합 - 1806

문제 링크

성능 요약

메모리: 41620 KB, 시간: 148 ms

분류

누적 합(prefix_sum), 두 포인터(two_pointer)

문제 설명

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

 

 

처음에 부분합 중 그 합이 S 이상이 되는 것 중 가장 짧은 것의 길이를 구한다는 문장만 보고 정렬하여 해결하는 방법을 생각했지만, '이 수열'에서 연속된 수들의 부분합 중에 구한다고 나와있어, 정렬은 할 수 없다는 것을 알게되었다.

그렇다면, 완전탐색을 돌리는 방법을 생각할 수 있는데 이 방법도 N의 범위가 100,000 까지 이므로, 시간초과가 난다는 것을 알 수 있다. 그러므로 시간 복잡도를 줄이기 위한 알고리즘이 필요하다는 것을 알 수 있었고, 그 중 투 포인터 알고리즘이 이 문제를 푸는 방법이 될 수 있다.

 

-구현 순서

1. 조건을 만족하는 가장 짧은 길이의 연속된 누적합을 구하기 위한 투 포인터를 정해야 하므로, 가장 왼쪽 포인터(left)와 조건을 만족할 때까지 증가할 오른쪽 포인터(right)를 맨 처음 인덱스인 0으로 두고 시작한다.

2. 최대 길이를 판단하기 위해 n의 범위보다 1 큰 100001을 답을 구하기 위한 ans 변수에 담는다.

3. 연속된 누적합을 담을 add 변수를 만들고, 제일 처음 값이 조건을 만족할 수 있으므로 add에 처음부터 넣어준다.add = (arr[0])

4. 오른쪽 포인터(right)가 배열 길이의 끝 지점(n)에 도달할 때까지 while문을 실행한다.

5. 누적합(add)이  s 이상일 시 기존에 저장된 길이(ans)와 현재 길이를 비교하여 최솟값을 ans에 초기화한다.

6. 최소 길이를 구하기 위해 왼쪽 포인터(left)를 증가시켜 조건을 만족하는 더 짧은 길이의 누적합이 있는지 확인한다.

7. 누적합(add)이 s 미만일 시 오른쪽 포인터(right)를 증가시켜 조건을 만족할 때까지 누적합(add += arr[right])을 계속 구한다.

8. while문이 종료되고, 구한 누적합(ans)이 처음에 100001로 저장한 그대로라면, 조건에 맞는 결과값이 없다는 뜻이므로, 0을 출력해주고 그게 아니라면, 최소 길이를 구한 결과값이 저장된 ans를 출력한다.

 

n, s = map(int,input().split()) #길이, 합
arr = list(map(int,input().split()))
left, right = 0, 0
ans = 100001
add = arr[0] #연속된 누적합

while True:
    if add >= s: #누적합이 원하는 값(s) 이상이면
        add -= arr[left]
        ans = min(ans, right - left + 1) #최소 길이
        left += 1
    else:
        right += 1
        if right == n: #끝 지점까지 도달 시 break
            break
        add += arr[right]

if ans == 100001:
    print(0)
else:
    print(ans)