[백준] 1806 부분합 / 투포인터 / Python 골4

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

 

 

이중 for문으로 그대로 구현했을 때는 시간초과가 떴다

<틀린코드>

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

a = list(map(int,input().split()))

# 연속 부분합 중 합이 s가 되는 것 중 가장 짧은 것


l=100001
for i in range(n):
    tl=0
    r=0
    for j in range(i+1,n):
        tl+=1
        r+=a[j]
        if r>=s:
            l = min(l,tl)
            break
print(l)

 

반복문은 한 번만 돌려야 0.5초 제한을 맞출 수 있을 것 같았음

 

두루뭉술하게 떠올렸을 때

쭉 선형 탐색을 하면서 누적합을 하는데,

최소 길이 규정 때문에 이전에 더했던 값을 빼면서 다음 값을 탐색해야 하나..막연히 생각하다가

 

결국 다른 풀이를 참고해보니

투포인터로 end,start를 조건에 따라 수동 업뎃하는 방식으로 풀어야 했다

 

while문을 돌면서

 

누적합이 목표보다 작은 경우에는 end 지점을 증가시키고,

(만약 end 지점이 n과 같다면 배열을 벗어난거니까 while문을 중지한다

누적합에 방금 업데이트한 end번째 값을 더한다

 

만약 누적합이 목표를 초과한 경우에는 목표를 달성한 것이기 때문에 길이 업데이트가 필요하다

그리고, 다음 탐색을 위해 가장 첫번째 더했던 원소를 빼줘야 한다

 

이전에 저장된 최소 길이와 현재 end와 start값으로 구할 수 있는 길이 값을 비교해서 min값으로 업데이트한다

첫번째에 더했던 원소를 빼줬으니까 start 값은 1 증가시켜서 옮겨준다

 

end가 n에 도달하면 while문이 끝난다

만약 이 상태에서 ans가 100001 그대로라면 부분합이 s에 도달할 수 없기 때문에 0을 출력

그 외에는 ans를 그대로 출력한다

 

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

partial = a[0]
ans=100001
start=0
end=0

while True:
    if partial<s:
        end+=1
        if end==n:
            break
        partial+=a[end]
    else:
        partial-=a[start]
        ans = min(ans,end-start+1)
        start+=1

if ans==100001:
    print(0)
else:
    print(ans)