백준 19951번 태상이의 훈련소 / C++ / 누적합 (Prefix Sum)

알고리즘 개념 누적합

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

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

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

 

백준 19951번 태상이의 훈련소 생활

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

19951번: 태상이의 훈련소 생활

문제

2020년 5월 14일 논산훈련소에 입대한 태상이는 첫 총기 훈련에서 가스 조절기를 잃어버리는 중대한 실수를 범했다. 그로 인해, 태상이는 조교들에게 눈총을 받게 되었다. 조교들은 태상이에게 연병장(운동장)의 흙을 옮기는 일을 주고 제대로 수행하지 못하면 징계를 내리려고 한다.

연병장은 일렬로 이어진N개의 칸으로 이루어져 있으며 각 칸마다 높이를 가지고 있고, 첫 번째 칸부터 순서대로 1번, 2번, 3번, ...,N번 칸으로 명칭이 붙어있다. 조교들은 총M명이 있으며, 각 조교들은 태상이에게a번 칸부터b번 칸까지 높이k만큼 흙을 덮거나 파내라고 지시한다. 흙은 주변 산에서 얼마든지 구할 수 있으므로 절대로 부족하지 않다.

태상이는 각 조교의 지시를 각각 수행하면, 다른 조교의 지시로 흙을 덮어둔 칸을 다시 파내기도 하는 비효율적인 일이 발생하는 것을 깨달았다. 그래서 태상이는 각 조교의 지시를 모아 연병장 각 칸의 최종 높이를 미리 구해 한 번에 일을 수행하려고 한다.

불쌍한 태상이를 위해 조교들의 지시를 모두 수행한 뒤 연병장 각 칸의 높이를 구하자.

입력

첫 줄에 연병장의 크기 N과 조교의 수M이 주어진다.

둘째 줄에 연병장 각 칸의 높이Hi가 순서대로N개 주어진다.

셋째 줄부터M개의 줄에 각 조교의 지시가 주어진다.

각 조교의 지시는 세 개의 정수a,b,k로 이루어져 있다.

• k ≥ 0인 경우a번 칸부터b번 칸까지 높이가 각각 |k| 만큼 늘어나도록 흙을 덮어야 한다.
• k< 0인 경우a번 칸부터b번 칸까지 높이가 각각 |k| 만큼 줄어들도록 흙을 파내야 한다.

출력

모든 지시를 수행한 뒤 연병장 각 칸의 높이를 공백을 사이에 두고 출력한다.

제한

• 1 ≤N≤ 100,000
• 1 ≤M≤ 100,000
• -10,000 ≤Hi ≤ 10,000
• N,M,Hi는 정수
• 조교의 지시
  • 1 ≤a ≤b ≤N

• • |k| ≤ 100

예제를 보려면 더보기 클릭

예제 입력 1

10 3
1 2 3 4 5 -1 -2 -3 -4 -5
1 5 -3
6 10 5
2 7 2

예제 출력 1

-2 1 2 3 4 6 5 2 1 0

---

문제 설명

예제를 보면 밑에 힌트가 나와있다.

• 초기 연병장의 상태: 1 2 3 4 5 -1 -2 -3 -4 -5
• 첫번째 지시 (1 5 -3)를 수행 한 뒤: -2 -1 0 1 2 -1 -2 -3 -4 -5
• 두번째 지시 (6 10 5)를 수행한 뒤: -2 -1 0 1 2 4 3 2 1 0
• 세번째 지시 (2 7 2)를 수행한 뒤: -2 1 2 3 4 6 5 2 1 0

먼저 첫번째 지시(1 5 -3)을 보면 a,b,k에서 -3은 0보다 작으므로 1번부터 5번까지 3만큼 흙을 파낸다. 즉 1~5번 구간을 모두 -3 해준다. 

두번째 지시(6 10 5)에서는 6~10번구간을 모두 5 만큼 더해준다. 라고 볼 수 있다. 

간단하게 생각하면 이것을 일일이 빼고 계산하는 방법이 있지만 연병장의 수와 조교의 수의 범위 최댓값이 100,000이다. 

만약 십만명의 조교가 모두 (1, 100000, 10)을 지시했다면 1번부터 100,000까지 모두 흙을 덮어줘야 한다.

연변장의 크기 100,000에 조교의 명령 100,000을 모두 수행하려면 총 100,000^2 만큼의 시간이 걸린다. -> 시간초과

따라서 사용하는 것이 누적합 알고리즘이다.

먼저 기존 값을 넣었던 배열이 아닌 누적합을 사용할 배열을 최대 크기로 만들어주자. 초기값은 0으로 초기화한다. 

arr	1	2	3	4	5	-1	-2	-3	-4	-5
cumarr	0	0	0	0	0	0	0	0	0	0

첫번째 지시 (1,5,-3)을 하려면 cumarr값이 다음과 같아야 한다. 

cumarr

-3

-3

-3

-3

-3

0

0

0

0

0

그러나 이것을 일일이 -3을 넣어주는 것이 아닌 누적합을 사용하는 것이다. 

바로 1(a)번째에는 -3을 6(b+1)번째에는 +3을 넣는 것이다.  

cumarr

-3

0

0

0

0

+3

0

0

0

0

이 상태에서 누적합을 사용하면 우리가 원했던 1~5번째에만 -3이 되는 결과를 얻을 수 있다. 

누적합 과정을 자세히 보고 싶다면 더보기 클릭

1. 첫번째 누적합은 그대로 내려온다

2. 첫번째 누적합과 기존의 두번째 값을 더해서 두번째 누적합을 만든다.

3. 위 과정을 반복한다.

4. 1~5번까지 -3인 누적합 배열 완성!

정리하자면 a부터 b까지 k만큼 하란 지시를 받았을때

a번째 값에는 +k를 b+1번째 값에는 -k를 해주는 것이 핵심이다. 

더 정확하게 설명하자면 인덱스는 0부터 시작하므로

a번째 인덱스인 a-1에 +k를 해주고, b+1번째 인덱스인 b에 -k를 해준다고 볼 수 있다. 

지시가 여러개이더라도 이 과정을 반복하여 누적합을 만들면 동일한 결과를 얻을 수 있다. 

---

제출한 코드(c++)

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, m;//연변장의 크기, 조교의 수
	cin >> n >> m;
	int arr[100005];
	int cumarr[100005]={0,};
	for (int i = 0; i < n; i++) {
		cin >> arr[i];//연변장의 각 높이
	}
	int a, b, k;
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> k;
		cumarr[a - 1] += k;
		cumarr[b] -= k;
		//누적합 배열 만들기
	}
	for (int i = 1; i < n; i++) {
		cumarr[i] += cumarr[i - 1];//누적합
	}
	for (int i = 0; i < n; i++) {
		cumarr[i] += arr[i];
	}
	for (int i = 0; i < n; i++) {//배열출력
		cout << cumarr[i] <<" ";
	}

	return 0;

}