[백준 1806 부분합] 파이썬 풀이 (골드 4)

https://www.acmicpc.net/problem/1806

---

문제 요약

연속된 수들의 부분합 중에서 합이 S 이상 되는 것 중 길이가 가장 짧은 것의 길이를 리턴

---

풀이

투 포인터 방식으로 풀 수 있다. 부분합이 s이상일 경우 최소 길이를 업데이트해주고, 왼쪽 포인터를 오른쪽으로 이동한다. 그리고 부분합이 s 미만일 경우 오른쪽 포인터를 오른쪽으로 이동한다. 즉, 윈도우를 늘여서 부분합을 증가시켜준다.

# 투 포인터
# 백준 1806 부분합
n, s = map(int, input().split())
nums = list(map(int, input().split()))

left = 0 # 왼쪽포인터
right = 0 # 오른쪽포인터
summation = 0 # 부분합
min_len = 100000001 # 문제 조건에 따른 최댓값 설정

while True:
    # 부분합이 s 이상일 경우 최소 길이를 업데이트 해주고,
    # 왼쪽포인터를 오른쪽으로 이동한 후 부분합도 그만큼 줄여준다.
    if summation >= s:
        min_len = min(min_len, right - left)
        summation -= nums[left]
        left += 1

    # 부분합이 s 미만일 경우 윈도우를 늘이며 부분합을 증가시켜준다.
    elif summation < s:
        # 오른쪽포인터가 n에 다다르면 더이상 진행이 불가하므로 중단.
        if right == n:
            break
        summation += nums[right]
        right += 1

if min_len == 100000001:
    print(0)
else:
    print(min_len)