[BOJ 19951] 태상이의 훈련소 생활

- 문제 요약

 

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

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

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

 

 

- 알고리즘 정리

 

문제에서 주어지는 a, b, k로 누적합 배열을 만들어 계산해 주면 됩니다.

새 배열을 하나 만들어서 a번째 칸과 b+1번째 칸에 k를 넣어준 후, 새로운 배열의 누적합을 구해서 원래 배열에 넣어주면 됩니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 100001
int n,m,arr[MAX],a,b,k,brr[MAX],co;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>m;
	for(int i=0;i<n;i++){
		cin>>arr[i];
	}
	for(int i=0;i<m;i++){
		cin>>a>>b>>k;
		brr[--a]+=k;
		brr[b]-=k;
	}
	for(int i=0;i<n;i++){
		co+=brr[i];
		arr[i]+=co;
		cout<<arr[i]<<" ";
	}
}

코드 제출 결과