[백준]2015수들의합 #map

1. 생각

수열의 연속합 중에서 특정 숫자를 만족하는 연속합을 찾는다.

(1) 수열의 요소들이 모두 양수가 아니기 때문에, 투포인터는 쓸 수 없고,

(2) N이 최대 200,000이므로 O(N)으로 끝내야한다.

​

2. 풀이

(1) 수열의 누적합을 계속해서 구한다.

(S[i] : 0에서부터 i까지의 누적합)

​

(2) i번째 숫자를 포함하는 연속합 중 K값이 되는 경우의 수는 S[i]-S[x]=K 를 만족하는 x의 개수와 같다.

(즉 S[x]=S[i]-K 를 만족하는 x의 경우의 수.)

​

(3) d라는 map을 관리하여 이를 바로 찾아준다

(d[a]=c : 누적합이 a가 되는 경우가 c개)

​

3. 소스코드

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

d={0:1}
cnt=0
S=0
for i in range(N):
    S += L[i]
    if S-K in d:
        cnt+=d[S-K]
    if S in d:
        d[S]+=1
    else:
        d[S]=1
        
print(cnt)