[백준]수들의 합2

문제 출처:

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

2003번: 수들의 합 2

---

오랜만에 알고리즘.. 빅리더 교육을 받은 9주 동안 못푼 문제들을 푸는 시간을 가졌다.

문제를 그냥 단순하게 이중 for문을 사용하면 끝날줄알았는데,

시간초과.. 이중 for문을 돌려도, index로 끊는다고 해도 시간초과가 났다..

결론은 아이디어가 문제였는데, for문을 돌다가 숫자가 원하는 m보다 작으면 끝나는 index를 늘려야했고, m보다 크면 시작 index를 당여오는 방식의 "두 포인터" 알고리즘을 써야했다.

import sys

n, m = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().rstrip().split()))
cnt: int = 0; start: int = 0; end: int = 1

while start <= end <= n:
    partial_sum = sum(a[start:end])
    if partial_sum < m:
        end += 1
    elif partial_sum > m:
        start += 1
    else:
        cnt += 1
        end += 1
print(cnt)