[백준 / 투 포인터] 2003 : 수들의 합 2 (python)

풀이

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
i,j,cnt,sum = 0,0,0,A[0]

while j != N:
    try:
        if sum < M:
            j+=1
            sum += A[j]
        elif sum > M:
            sum-=A[i]
            i+=1
        else:
            cnt+=1
            sum-=A[i]
            i+=1
            j+=1
            sum+=A[j]
    except IndexError:
        break

print(cnt)

• 투 포인터는 2개의 포인터로 알고리즘의 시간 복잡도를 최적화한다.
• 위 문제의 시간제한은 0.5초인데,  N, M의 범위 값이 각각 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이므로 반복문을 계속 돌려서 문제를 해결할 수 없다. 따라서 투 포인터를 사용한다.
• i, j는 각각 배열을 가리키는 포인터다.