[백준] 19951번. 태상이의 훈련소 생활 (C++)

문제

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

 

풀이

[누적합]

 

sum+=prefixSum[i] 이기 때문에

prefixSum의 시작점(예를들어 1번의 -3) 끝점(예를 들어 6번의 +3)에만 값들을 지정해 주면 된다.

 

시작점의 위치는 0부터 시작하게 했으므로 prefixSum[a - 1] += k;
끝점은 a~b에 k값을 더해야 하기 때문에 b-1이 아닌 b이다. prefixSum[b] -= k;

 

 

코드

#include <iostream>
#include <vector>
using namespace std;

int main() {
	
	//INPUT
	int N, M, a, b, k;
	cin >> N >> M;

	vector<int>ground(N, 0);
	for (int i = 0; i < N; i++) {
		cin >> ground[i];
	}

	vector<int>prefixSum(N+1, 0);
	for (int i = 0; i < M; i++) {
		cin >> a >> b >> k;
		prefixSum[a - 1] += k;
		prefixSum[b] -= k;
	}

	//CALCULATE
	int sum=0;
	for (int i = 0; i < N; i++) {
		sum += prefixSum[i];
		cout << ground[i] + sum << " ";
	}

	return 0;
}