백준 1806 부분합 G4

문제출처

생각

전형적인 투포인터 문제라고 한다.

투포인터란 N개의 리스트를 순회할 두개의 포인터위치를 기록하며 처리하는 알고리즘이다.

정렬되어있는 문제는 보통 이진탐색으로 답을 구하지만 투포인터로도 적용할 수 있다.

핵심은 다음과 같다.

start, end의 포인터를 첫 시작점으로 잡아놓고

찾아야하는 기준점(부분합)을 계속 더해나간다.

만약 기준보다 더해진 값이 작다면 end를 오른쪽으로 이동시킨다.

기준보다 커지면 반복문을 탈출하고 찾아야하는 기준에 부합하는지 확인한다.

그리고 start를 오른쪽으로 한칸 옮기며 반복을 이어나간다.

시간복잡도는 start는 0 ~ N까지 순회하기에 O(N)이고

end도 마찬가지로 0 ~ N까지 돌기에 O(N)이다.

결론은 O(N)의 시간복잡도를 갖는다.

문제에서 부합하는 답이 없다면 0을 리턴해야하기에 is_possible을 두고 최소값을 구할 때 True로 set했다.

코드

N, M = map(int, input().split())


lst = list(map(int, input().split()))

min_val = N
part_sum = lst[0]
is_possible = False
end = 1
for start in range(0, N):
    while end < N and part_sum < M:
        part_sum += lst[end]
        end += 1
    if M <= part_sum:
        min_val = min(min_val, end - start)
        is_possible = True
    part_sum -= lst[start]
if is_possible:
    print(min_val)
else:
    print(0)