BOJ 1806 - 부분합

문제

백준 온라인 저지 - 1806번

풀이 과정

투 포인터 를 활용해서 연속된 수열의 합이 S 이상인 구간 중 가장 길이가 짧은 구간을 찾는 문제입니다.

모든 숫자가 양의 정수이므로 두 개의 포인터 head, tail 을 사용해서 합이 S 보다 커질 경우 head 를 증가시키고

S 보다 작아질 경우 tail 을 증가시키면 됩니다.

코드

import sys

N, S = list(map(int, sys.stdin.readline().split()))
nums = list(map(int, sys.stdin.readline().split()))


def solution():
    answer = sys.maxsize
    head, tail = 0, 1
    acc = nums[head] + nums[tail]

    while head <= tail:
        if acc < S:
            tail += 1
            if tail < N:
                acc += nums[tail]
            else:
                break
        else:
            answer = min(answer, tail - head + 1)
            acc -= nums[head]
            head += 1

    return answer if answer != sys.maxsize else 0


print(solution())