백준 11441번 합 구하기 / C++ / 누적합 (Prefix Sum)

 

알고리즘 개념 누적합

누적합에 대해 잘 모른다면 이전에 정리해 둔 개념 정리를 한번 읽어보고 오는 것을 추천합니다.

[알고리즘] 누적합 (prefix sum)

 

[알고리즘] 누적합 (prefix sum)

 

백준 11441번 합 구하기

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

11441번: 합 구하기

문제

N개의 수 A1, A2, ..., AN이 입력으로 주어진다. 총 M개의 구간 i, j가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄에는 A1, A2, ..., AN이 주어진다. (-1,000 ≤ Ai ≤ 1,000) 셋째 줄에는 구간의 개수 M이 주어진다. (1 ≤ M ≤ 100,000) 넷째 줄부터 M개의 줄에는 각 구간을 나타내는 i와 j가 주어진다. (1 ≤ i ≤ j ≤ N)

출력

총 M개의 줄에 걸쳐 입력으로 주어진 구간의 합을 출력한다.

예제 입력 1

5
10 20 30 40 50
5
1 3
2 4
3 5
1 5
4 4

예제 출력 1

60
90
120
150
40

예제 입력 2

3
1 0 -1
6
1 1
2 2
3 3
1 2
2 3
1 3

예제 출력 2 

1
0
-1
1
-1
0

---

문제 설명

사실 위 문제는 저번에 풀었던 백준 11659번 구간 합 구하기 4 (C++)에서 썼던 코드를 약간만 수정하여 제출하였다. 

그만큼 똑같은 문제이나 누적합을 처음 배우는 입장에서는 헷갈릴 수 있으니 같은 문제도 반복해가며 연습하는게 좋다. 

먼저 누적합을 사용하는 과정부터 살펴보자면 (예제 1번)

예제 누적합 설명1

예제 누적합 설명2

예제 누적합 설명3

예제 누적합 설명4

사진에서는 보기 편하게 cumarr이라는 배열을 새로 만들었으나 내 코드에서는 기존 arr값에 누적해서 더하는 방식으로 코드를 짰다. 

해당 arr의 값에서 이전의 값들을 모두 더해주는 식으로 구성한 것이다. 

for (int i = 1; i < n; i++) {
	arr[i] += arr[i - 1];
}

만약 새로운 배열을 이용한다면 이런식으로 코드를 짜도 될 것이다. 

for (int i = 1; i < n; i++) {
	cumarr[i] = arr[i];
    	cumarr[i] += arr[i-1];
}

그럼 이제 이렇게 만든 누적합 배열을 이용해서 답을 구해보자.

1~3일때 10+20+30=60이다. 이것은 누적합 배열에서도 1~3까지 다 더한 값 인덱스 2번에서 얻을 수 있다. 

2~4일때 20+30+40=90이다. 누적합 배열에서는 1~4까지 더한 값에서 1을 빼주면 된다. 

인덱스 3번(100)-인덱스 1번(10)=90 으로 값을 구할 수 있다.

3~5일때도 마찬가지로 30+40+50=120을 1~5까지 더한 값에서 1~2까지 더한 값을 빼준다. 

인덱스 4번(150)-인덱스 1번(30)=120

4~4일때는 원래 그냥 4로 구할 수도 있지만 우리는 누적합을 쓰고 있으니까 1~4까지 더한 값에서 1~3까지 더한 값을 빼주면 된다. 

인덱스 3번(100)-인덱스 2번(60)=40 

정리하자면 i와 j가 주어졌을때 i에서 j까지 더한 값을 구하는 공식은 다음과 같다. 

arr[j-1]-arr[i-2]

여기서 i의 범위는 1이상이므로 i가 1일때는 위 공식을 사용하는 것이 아닌 arr[j-1]만 해주면 된다. 

어쩌다보니 이전 알공 3주차(01)과 설명이 많이 똑같아졌는데 솔직히 같은 문제라고 봐도 될 정도로 비슷한 문제들이라 어쩔 수 없는 것 같다.. 

---

제출한 코드(C++)

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long int;
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int arr[100005];
	int n, m;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	for (int i = 1; i < n; i++) {
		arr[i] += arr[i - 1];
	}
	cin >> m;
	int a, b;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		if (a >= 2) {
			cout << arr[b - 1] - arr[a - 2] << "\n";
		}
		else
			cout << arr[b - 1] << "\n";
	}
}