[백준] 1806번: 부분합

문제

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

1806번: 부분합

 

풀이

투 포인터를 사용해 풀었습니다.

• left, right을 0으로 초기화합니다.
• right가 0부터 N까지 아래 작업을 반복합니다.
  • 누적합(total)이 S 미만이면 누적합에 nums[right]를 더합니다.
  • 누적합이 S 이상이면 미만이 될 때까지 아래 작업을 반복합니다.
    • 최소 길이를 저장합니다.
    • 누적합에서 num[left]를 뺍니다.
    • left를 1 증가시킵니다.
  • right를 1 증가시킵니다.

 

코드

파이썬

import sys

input = sys.stdin.readline
INF = sys.maxsize

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

answer = INF
total = 0
left = 0
for right in range(N):
    if total < S:
        total += nums[right]
    while total >= S:
        answer = min(answer, right - left + 1)
        total -= nums[left]
        left += 1

print(answer if answer != INF else 0)