[Python/파이썬] 백준 1806번 - 부분합

문제 설명

 

입출력 예제

 

1806번: 부분합

---

풀이 코드

배열에서 특정한 합을 갖는 부분 연속 수열을 찾는 것은 투 포인터 알고리즘을 활용하는 대표적인 예이다.

투포인터 알고리즘에 대한 설명은 아래 링크를 통해 확인 할 수 있다.

[알고리즘] 투 포인터(Two Pointers)란?

 

정답 코드

import sys
input = sys.stdin.readline

N, S = map(int, input().strip().split())
nums = list(map(int, input().strip().split()))

total = 0 # 부분합
start = 0
end = 0
min_len = 1e9

while True:
    # 현재 부분합이 찾고자하는 값보다 크거나 같다면
    if total >= S: 
        min_len = min(min_len, end - start) # 가장 짧은 길이 갱신
        total -= nums[start]
        start += 1

    # 현재 부분합이 찾고자하는 값보다 작다면
    elif total < S:
        if end == len(nums):    # 배열의 끝까지 탐색했다면 종료
            break
        total += nums[end]
        end += 1

if min_len == 1e9:
    print(0)
else:
    print(min_len)