[C++]백준 - 11659번 문제

11659번: 구간 합 구하기 4 (acmicpc.net)

11659번: 구간 합 구하기 4

 

11659번 : 구간 합 구하기 4

---

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

 

 

 

출력

---

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

 

 

 

---

 

생각해 볼 점

---

누적 합 문제입니다.

 

누적합은 배열 요소를 계속 더해 나간 배열을 의미합니다.

 

예시)

 

기존 배열

index	0	1	2	3	4
value	5	2	8	9	1

누적합 배열

index	0	1	2	3	4
value	5	7	15	24	25

 

누적합을 쓰는 이유는 구간 합을 구하기 편하기 때문입니다.

 

예를 들어, index {1 ~ 3}까지의 합을 구하고 싶다면

 

누적합 배열에서

sum_arr[3] - sum_arr[0] = 19 입니다.

 

즉 {i ~ j} 까지의 구간은

 

sum_arr[j] - sum_arr[i - 1] 입니다.

 

코드

---

#include <iostream>
int main()
{
	int N, M;
	scanf("%d %d", &N, &M);

	int arr[100001];
	arr[0] = 0;
    
    //누적 합
	for (int i = 1; i <= N; i++)
	{
		scanf("%d", &arr[i]);
		arr[i] += arr[i - 1];
	}
    
    //출력부
	while (M--)
	{
		int i, j;
		scanf("%d %d", &i, &j);
		printf("%d\n", arr[j] - arr[i - 1]);
	}
	return 0;
}

 

그 외

---