투 포인터

투 포인터

1806번 - 부분합

문제

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

입력

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

출력

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

수열의 첫번째 값을 두개의 포인터가 가르키고 있는 상태로 시작한다. 위의 예제에서는 5로 시작하고 5만 포함 된 부분 수열의 합은 5이다.

부분 합이 입력으로 주어진 S(예제에서는 15)이상이 될 때 까지 부분 수열에 값을 하나씩 추가한다.

5부터 10까지의 부분 수열이 됐을 때 부분 수열의 합이 15을 넘게 된다. 문제에서 요구하는 것은 부분 합 S를 만족하는 가장 짧은 부분 수열이기 때문에 이제는 S이상을 만족할 때 까지 S를 한 칸씩 움직이며 길이를 줄여 나가야 한다.

왼쪽 끝을 5까지 이동하고 나면 조건을 충족하면서 가장 짧은 부분 수열일 수도 있는 부분 수열 하나를 구할 수 있게 되었다.

값이 정렬되어 있는것이 아니기 때문에 더 짧은 부분 수열이 오른쪽에 존재 할 수 있다.

그래서 부분 수열의 시작 지점을 하나 늘려 위의 작업을 S가 수열의 끝에 도달 할 때까지 이 작업을 반복한다.

이렇게 시작과 끝을 가르키는 포인터 두 개를 사용해 조건에 맞는 값들의 모음들을 탐색하는 문제들을 투 포인터(두 포인터)라고 한다. 문제에 따라서 포인터의 시작위치와 포인터들을 움직이는 방식들을 응용해 풀어야 한다.

구현

from sys import stdin
n, s = map(int, stdin.readline().split())
arr = list(map(int, stdin.readline().split()))
if(sum(arr) < s): print(0) # 전체 수열의 합이 S보다 작으면 불가능하기 때문에 0을 출력
else:
    left = 0
    right = 0
    answer = n
    length = 1
    total = arr[left]
    while(left < n):
        if(total < s):
            right += 1
            if(right >= n): break
            total += arr[right]
            length += 1
        else:
            answer = min(answer, length)
            if(answer == 1): break # 1보다 작은 경우는 존재하지 않기 때문에 더 이상 탐색할 필요가 없다.
            total -= arr[left]
            l -= 1
            left += 1
    print(answer)