BOJ 2015 수들의 합 4

이 문제는 주어진 수열에서 연속된 부분 수열의 합이 k가되는 연속된 부분 수열의 개수를 구하는 문제인데, 자기 자신(즉 i부터 i까지)만 선택하는 것도 가능하기 때문에
여기서 연속된 부분 수열의 합의 가지수는 n+(n-1)+...+1 = n*(n+1)/2 가지이다.

질문 게시판의 답변을 보니 풀이에 대한 설명이 있었고 참고해서 풀었다.

수열의 각 수까지의 부분합(1~n번째 수까지 합)을 O(N)만에 구할 수 있다. 부분합을 미리 구해놓으면, 예를 들어 연속된 부분 수열의 합 a[i]~a[j]까지의 합은 psum[i]-psum[j-1]로 O(1)만에 구할 수 있다. 즉 psum[i]-psum[j-1]=k인 경우의 수를 구하면 되는데, 수열의 첫 번재 수 x부터 살펴보면서 그 수의 psum과 k를 비교하고, 또한 psum[x]-psum[y]=k가 되는 psum[y]의 개수를 구하면 되는데, 즉 psum[y]=psum[x]-k 인 psum[y]의 개수를 찾으면 되는데 일일이 찾다가는 O(N제곱)이 될 것이다. 그래서 앞에서부터 보면서 그 때까지 나온 psum값의 개수를 기록해놓는다. 여기서 만약 배열을 쓸 경우, psum의 범위는 최대 20억이므로 메모리 초과가 날 것이다. 그렇기 때문에 map을 활용한다! map을 활용하면 psum의 개수만큼 늘어나므로 psum의 개수는 20만개밖에 안되기 때문에 충분하다.

여기서 map<int, long long>으로 해줬는데, map<부분합, 해당 부분합의 개수> 이므로 각각 최대 20억, 20만개일 것이다. 하지만 최종 답을 구할 때는 개수를 더하다보면 int형 범위를 넘어갈 수 있으므로, 해당 부분합의 개수 부분은 계산할 때 편하게 long long으로 해줬다. int로 해도 덧셈연산을 할때 (long long)형변환을 해주면 가능하다.

백준님 풀이
수가 자연수일 때는 투 포인터로 구할 수 있다. 차이가 커지고, 적어지는게 자연수이므로 분명하다. 하지만 이 문제는 음수와 0이 있어서 다른 방법을 써야한다.

0이되는 구간의 개수를 이용한다... 누적합을 이용한다.
map을 쓰는 것이 좋다.
매우 중요한 문제이다. 이 방법을 그대로 이용하는 문제로는
나머지 합이라는 문제가 있다. 10986번.

참고로 만약 찾으려고 하는 k가 0일때는 nC2들의 합을 구해버리면 된다. 나머지 합이라는 문제도...