[백준] 2015번 수들의 합 4 - 파이썬/해시

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

from collections import defaultdict

N,K = map(int,input().split())

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

DP = [A[0]]*N

history = defaultdict(int)

history[A[0]]=1

ans = 0

for i in range(1,N):

    DP[i]=DP[i-1]+A[i]

    if (DP[i]-K) in history:

        ans+= history[DP[i]-K]

    history[ DP[i] ] +=1

for i in DP:
    if i==K:
        ans+=1

print(ans)

얼마전에 구름 알고리즘 강의에서 defaultdict 에 대해 배워서 딕셔너리 문제를 풀었다.

범위가 일반적인 누적합 알고리즘으로 풀면 시간초과나 메모리초과가 발생할 수 있어서 딕셔너리를 활용하여 풀었다.