[투포인터] 백준-1806 부분합 골드4 (Python)

백준-1806 : 부분합

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

1806번: 부분합

 

 

 

풀의

• 입력 받은 값의 구간합 배열을 만든다.
• 투포인터를 이용하여 왼쪽은 구간합 시작점 오른쪽은 구간합의 끝점으로 사용한다.
  • 구간합의 값이 S 보다 작을 경우 오른쪽 포인터를 이동
  • 목표 합 보다 크고 길이가 짧은 경우 정답을 갱신
  • 구간합의 값이 S 보다 클 경우 왼쪽 포인터를 이동 한다.
• 구간 합을 못찾을 경우 0을 반환

 

코드 (Python)

import sys

def input():
    return sys.stdin.readline().rstrip()

n, s = map(int, input().split())

numList = list(map(int, input().split(" ")))
sumList = [0] * (n + 1)

result = n + 1
rightIndex = 0

for i in range(n):
    sumList[i + 1] = sumList[i] + numList[i]

for leftIndex in range(n):
    # 구간합이 목표 보다 작을 경우 오른쪽 index 증가
    while rightIndex < n and sumList[rightIndex + 1] - sumList[leftIndex] < s:
        rightIndex += 1
    # 구간합 목표를 달성하면 정답 갱신
    if rightIndex < n and sumList[rightIndex + 1] - sumList[leftIndex] >= s:
        result = min(result, rightIndex - leftIndex + 1)

# 구간합을 못찾을 경우
if result > n:
    result = 0

print(result)