BOJ 2015 수들의 합 4
·
알고리즘/BOJ
www.acmicpc.net/problem/2015 2015번: 수들의 합 4 첫째 줄에 정수 N과 K가 주어진다. (1 ≤ N ≤ 200,000, |K| ≤ 2,000,000,000) N과 K 사이에는 빈칸이 하나 있다. 둘째 줄에는 배열 A를 이루는 N개의 정수가 빈 칸을 사이에 두고 A[1], A[2], ..., A[N]의 순서로 � www.acmicpc.net 각각 i부터 j까지의 부분합 중 k인 수가 몇 개인지 세는 문제이다. 일단 prefix sum을 통해서 배열을 채웠는데 for (int i = 1; i > x; d[i] += d[i - 1] + x; } 이 후가 문제이다. 여기서 각각의 원소에 대해서 \(O(N^2)\) 으로 짜면 시간 초과가 난다. 따라서 i 부터 j 사이의 부분합의 개수..