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

문제 소개

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

• 태상이는 훈련소에서 삽질을 하는데, 조교들이 각각 a 부터 b까지 무작위로 땅을 c칸 파라고 명령한다.
• 여기서 c는 +일지 -일지 알 수 없기 때문에 태상이는 각 칸마다 최종 높이를 미리 계산해서 일을 한번에 하려고 한다.
• 연병장의 크기와 조교의 명령 횟수는 각각 100,000이기 때문에 단순 완탐이 아닌 다른 방법으로 풀어내라

접근 방법

• 사실 이 문제 해결방법이 1시간 넘게 떠오르지 않아 다른 블로그의 풀이를 참고했다.
• 내가 그동안 풀었던 누적합 문제는 내가 미리 누적합을 구해두고 연산할 때 활용하는 방식으로 연산수를 줄이는 방식이었다.
• 하지만 이 문제는 마지막에 누적합을 수행했을 때 각 칸에서 최종적으로 몇 칸씩 더 파거나 더 쌓아야하는지 계산할 수 있도록 누적합을 할 배열의 수를 적절히 조절하는 것이 포인트였다.
• 누적합을 구해서 활용하는 것이 아닌, 누적합을 진행했을 때 올바른 배열이 완성되도록 식을 세우는 방법도 있다는 것을 배웠다.
• 어쨌든 일정 구간에서 일정한 동작을 반복해서 수행해야하는 문제는 누적합으로 접근하는 게 맞다는 것을 알 수 있었다.

풀이법

• 100,000번이니까 시간복잡도를 nlog n이나 n으로 접근해야하는데, 누적합을 이용해서 n으로 풀이한다.
• 1부터 3까지 +2라면 누적합 배열을 [2,0,0,-2,0,..., 0]으로 설정해둔다.
• 그럼 나중에 해당 누적합 배열에서 누적합을 수행하면 [2,2,2,0,0...,0]으로 변하게 되고, 이를 원래 입력받은 초기 배열에 더하면 된다.

코드

#include <iostream>

using namespace std;

int    ground[100001];
int    total[100001];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, start, end, count;
    int sum = 0;

    cin>>N>>M;
    for (int i = 0; i < N; i++)
    {
        cin>>ground[i];
    }
    for (int i = 0; i < M; i++)
    {
        cin>>start>>end>>count;
        total[start - 1] += count;
        total[end] += -1 * count;
    }
    for (int i = 0; i < N; i++)
    {
        sum += total[i];
        cout<<sum + ground[i]<<" ";
    }
    cout<<endl;
}