[백준] 2015번: 수들의 합(python)

2015번:  수들의 합

---

문제 )

A[1], A[2], ..., A[N]의 N개의 정수가 저장되어 있는 배열이 있다. 이 배열 A의 부분합이란 1 ≤ i ≤ j ≤ N인 정수 i와 j에 대해 A[i]부터 A[j]까지의 합을 말한다.

N과 A[1], A[2], ..., A[N]이 주어졌을 때, 이러한 N×(N+1)/2개의 부분합 중 합이 K인 것이 몇 개나 있는지를 구하는 프로그램을 작성하시오.

 

 

 

입력 :

첫째 줄에 정수 N과 K가 주어진다. (1 ≤ N ≤ 200,000, |K| ≤ 2,000,000,000) N과 K 사이에는 빈칸이 하나 있다. 둘째 줄에는 배열 A를 이루는 N개의 정수가 빈 칸을 사이에 두고 A[1], A[2], ..., A[N]의 순서로 주어진다. 주어지는 정수의 절댓값은 10,000을 넘지 않는다.

 

 

 

출력 :

첫째 줄에 합이 K인 부분합의 개수를 출력한다.

 

 

 

풀이)

특정 누적합에서 k를 빼면 있는 cnt의 값을 더해주는 식으로 문제를 풀어야 했다.

아래의 코드로 예제 2번의 cnt를 만들어보면

 

cnt[1] : 1

cnt[3] : 1

cnt[6] : 1

cnt[10] : 1

cnt[15] : 2

 

가 나오게 되고, 코드가 진행됨에 따라, 

i = 3이면 ans += cnt(6 - 5) = 1

i = 5이면 ans += cnt(15 - 5) = 1

i = 6이면 ans += cnt(15 - 5) = 1

이므로 ans = 3이 나오게 된다.

 

n, k = map(int, input().split())
li = [0] + list(map(int, input().split()))
# 누적합 배열 생성
prefix = [0] * (n + 1)
 
# 갯수를 세서 담을 딕셔너리
cnt = {}
# 딕셔너리 만들기
for i in range(1, n + 1):
    prefix[i] = prefix[i - 1] + li[i]
 
 
ans = 0
for i in range(n + 1):
    # cnt 딕셔너리에서 prefix[i] - k의 수를 ans에 넣어준다.
    # 해당 값이 없으면 0을 넣음.
    ans += cnt.get(prefix[i] - k, 0)
    # 해당 값이 없으면 1을 생성해 넣어주고, 있으면 1을 더 해준다.
    cnt[prefix[i]] = cnt.get(prefix[i], 0) + 1
    
print(ans)

---

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

2015번: 수들의 합 4