1806번 부분합(Gold4)

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

1806번: 부분합

import sys

n,s=map(int,sys.stdin.readline().split())

array=list(map(int,sys.stdin.readline().split()))

cnt=0
start=0
end=0
total=0
minimum=int(1e9)
while end!=n:
    if array[end]>=s:
        minimum=1
        break
    if total<s:
        total+=array[end]
        end+=1
        cnt+=1
    else:
        total-=array[start]
        start+=1
        cnt-=1
    if total>=s and cnt<minimum:
        minimum=cnt
    if end==n:
        if minimum==int(1e9):
            minimum=0
            break
        while total>s:
            total -= array[start]
            start += 1
            cnt -= 1
            if total >= s and cnt < minimum:
                minimum = cnt
print(minimum)

투포인터와 부분합 개념을 이용하여 푸는 문제였다.

 

계속 74%에서 틀렸습니다가 나와 고민을 했었는데,

반례 중

4 5

1 2 2 3

답: 2

에서 막히는 것을 알 수 있었다.

end==n이 되었을 경우 total>s이더라도 start를 늘려나가는 작업을 수행하지 않아 발생한 문제였다.