[C++]백준 11659번 구간 합 구하기 4

[C++] 백준 11659번 구간 합 구하기 4

https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

• 난이도: 실버 3
• 알고리즘 분류:  누적합
• 문제: 수 N개가 주어졌을 때 i부터 j까지의 수의 합 구하기.
• 입력: N, M과 N개의 수 그리고 M개의 i, j가 입력된다.
• 출력:M개의 줄에 i 부터 j까지의 합을 출력한다.
• 해결:. 누적합을 사용하여 해결한다. 입력을 받을 때마다 이전 모든 값을 합을 sum에 저장하고 출력할 때 sum [j] - sum [i-1]을 계산한 값을 출력한다.
• 주의할 점: 매번 i부터 j까지의 합을 계산한다면 O(N^2)의 시간복잡도가 걸리므로 시간 초과가 된다. 또 sum에 값을      저장할 때 0번째부터가 아닌 1번째부터 계산하여 sum [0]에 0이 들어가 록 한다.

#include <iostream>
using namespace std;

int sum[100000];
int main() {
	int N, M;
	scanf("%d %d", &N, &M);

	for (int i = 0; i < N; i++) {
		int q;
		scanf("%d", &q);
		sum[i + 1] = sum[i] + q;//0부터 i까지의 수를 sum에 저장
	}

	for (int i = 0; i < M; i++) {
		int x, y;
		scanf("%d %d", &x, &y);

		printf("%d\n", sum[y] - sum[x - 1]);
	}
}

깔끔하게 ㄲㅡㅌ