[파이썬] 백준 1806 : 부분합 (골드4)

[파이썬] 백준 1806 : 부분합 (골드4)

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

---

풀이

방향성 생각

• $N=10^{6}$이라 $N^2$로는 불가능하다.
• 투포인터를 통해서 한쪽 피벗에서 누적 합을 기록하며 목표값을 넘는 순간 값을 기록한다.

---

전체코드

N,goal = map(int,input().split())
arr = list(map(int,input().split()))

l,r = 0,0
carr = 0
answer = N+1
while True:
    if carr >= goal:
        answer = min(answer,r-l)
        carr -= arr[l]
        l += 1
    elif r == N:
        break
    else:
        carr += arr[r]
        r += 1

print(answer if answer != N+1 else 0)

코멘트

• .