코딩테스트
[백준 11659] 구간 합 구하기 4 c++ (구간합)
문제 링크 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 문제 해설 기본적인 dp 문제이다. a~b 까지의 합을 구하는 방법을 0~b까지의 누적합 - 0~a까지의 누적합 으로 구하면 매번 구간합을 구하는 시간 복잡도가 j-i 번 -> 2번으로 바뀐다. 정답 코드 #include using namespace std; int arr[100001]; int sum[100001]; //누적합 int main() { int n,..
