[Python] 백준(BOJ) 1806번: 부분합 - 투포인터 알고리즘

문제

1806번: 부분합

풀이

2003번(yuuj.tistory.com/160)과 비슷하게 투포인터 알고리즘으로 풀면 되는데, 주의해야할 점은

 

1. 합이 S와 일치하는 경우가 아닌, S이상일 경우이라는점

2. 가능하지 않을 경우엔 0을 리턴해야한다는점이다.

 

문제 제대로 읽기 !!!!!

import sys

N, S = map(int, sys.stdin.readline().split(" "))
arr = list(map(int, sys.stdin.readline().split(" ")))

start = 0
end = 1
result = N
sum = arr[start]
if sum == S:
    result = 1
flag = 0

while not (start == end == N):
    if sum < S and end < N:
        sum += arr[end]
        end += 1
    else:
        sum -= arr[start]
        start += 1

    if sum >= S:
        result = min(result, end-start)
        flag = 1

if flag == 0:
    print(0)
else:
    print(result)