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

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

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

 

 이번 문제는 N개의 초기 흙더미의 높이 혹은 구덩이의 깊이가 주어지고 M개의 변화가 주어졌을 때, 최종 결과를 출력하는 문제이다. 이 문제는 어렵게 생각할 것 없이 조교의 지시 사항이 주어질 때마다 변경하여도 해결할 수 있다. 하지만 이럴 경우 시간초과에 의해 문제를 해결할 수 없을 수도 있다. 왜냐하면 1번부터 100,000번까지의 변화를 요구하는 100,000개의 지시가 주어지는 최악의 경우에는 단순히 생각해도 매우 많은 시간이 필요하기 때문이다. 그렇기에 누적합을 이용하여 푸는 것이 적절하다.

 누적합은 프로그래머스의 '파괴되지 않은 건물'(https://school.programmers.co.kr/learn/courses/30/lessons/92344) 문제에서도 살펴 보았다. 주어진 예제의 첫 번째 지시를 보자. 1번부터 5번까지 -3만큼 높이를 변화하라고 하였다. 이럴 경우, 단순하기 [-3, -3, -3, -3, -3]이 아닌, [-3, 0, 0, 0, 0, 3](시작 인덱스의 값은 주어진 값인 -3으로, 마지막 인덱스 + 1의 값은 -주어진 값인 3으로)으로 저장하면 된다. 그리고 계산하기 직전, 누적합의 i번째 변화값은 누적합[i] += 누적합[i - 1]로 구할 수 있다. 즉, [-3, 0, 0, 0, 0, 3]은 답을 구하기 직전에 [-3, -3, -3, -3, -3, 0]으로 변화시킨 후 계산한다. 지시가 여러 개여도 이와 같이 누적합[시작인덱스]에 주어진 값을 더하고 누적합[마지막인덱스 + 1]에는 주어진 값을 빼서 저장한다. 즉, 예제의 경우에는 누적합이 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] -> [-3, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0] -> [-3, 0, 0, 0, 0, 8, 0, 0, 0, 0, -5] -> [-3, 2, 0, 0, 0, 8, 0, -2, 0, 0, -5]이다. 그리고 답을 계산하기 직전 누적합을 정리하면 [-3, -1, -1, -1, -1, 7, 7, 5, 5, 5, X]이다. (11번째 값은 누적합 계산을 위해 편의상 추가한 것이므로 X라고 적었음)

 

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <memory.h>
#include <deque>
#include <cmath>
#include <stack>
#include <cstring>
#include <typeinfo>
#include <iomanip>
#include <limits.h> 
#include <map>
#pragma warning(disable:4996)

using namespace std;

#define MAX 100001

int N, M;
int heights[MAX];
int orders[MAX];

int main()
{
	ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	cin >> N >> M;

	for (int i = 1; i <= N; ++i)
		cin >> heights[i];

	for (int i = 0; i < M; ++i)
	{
		int start, end, change;
		cin >> start >> end >> change;

		orders[start] += change;
		orders[end + 1] -= change;
	}

	for (int i = 2; i <= N; ++i)
		orders[i] += orders[i - 1];

	for (int i = 1; i <= N; ++i)
	{
		heights[i] += orders[i];
        printf("%d ", heights[i]);
	}

	

    return 0;
}