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

 

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

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

 

문제 분석

배열에서 일정 범위 a~b에 정수 k를 더하는 명령을 여러 번 수행하는 문제입니다. 단순히 매 명령마다 배열에서 a~b까지 k를 더하도록 구현하면 시간복잡도가 O(NM)이 되어 시간 안에 문제를 풀 수 없습니다.

더 좋은 방법은, 명령의 범위 a, b와 더할 숫자 k를 기록하는 배열을 만들고, 누적합을 이용하여 원래 배열에 더해주는 것입니다. 이렇게 구현하면 시간복잡도는 O(N+M)으로 줄어들게 됩니다. 자세한 설명은 아래와 같습니다.

문제의 예제에서 a=1, b=5, k=-3의 명령을 기록한 배열의 모습입니다. a에 k, b+1에 -k를 기록하고 1부터 누적합을 구하면, 이 누적합이 a부터 b까지 k를 더하는 명령과 같다는 것을 알 수 있습니다.

예제에서 주어진 세 가지 명령을 모두 기록하고, 누적합을 원래 배열에 더해주면 답을 구할 수 있습니다.

 

코드

#include<iostream>

using namespace std;

int N, M, H[100000], a, b, k, o[100001], sum=0;

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin>>N>>M;

    for(int i=0; i<N; i++) cin>>H[i];

    for(int i=0; i<M; i++)
    {
        cin>>a>>b>>k;
		// 명령을 기록합니다 저는 0번 인덱스부터 시작했습니다.
        o[a-1]+=k;
        o[b]-=k;
    }
    
    for(int i=0; i<N; i++)
    {
        sum+=o[i]; // 명령의 누적합입니다.
        H[i]+=sum; // 누적합을 원래 배열에 더해줍니다.
        cout<<H[i]<<' ';
    }

    return 0;
}