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

백준의 태상이의 훈련소 생활(19951) 문제이다.

 

[ 문제풀이 ]

매우 간단하게 풀 수도 있는 문제이지만, 자칫하면 시간초과에 걸릴 수 있는 문제이다.

간단하게 풀었을 때의 문제점과 이를 해결하기 위한 방법에 대해서 먼저 이야기 해보고, 그 이후에 정답을 도출해보자.

 

#1. 간단한 접근

먼저, 문제에 가장 쉽게 접근해보자. 조교 한명 한명의 지시가 떨어질 때 마다 업데이트를 계속해서 해주는 것이다.

예를 한번 들어보자.

연병장의 각 칸의 높이가 [ 1 , 2 , 3 , 4 , 5 ] 라고 주어졌다고 가정해보자.

이 때, 조교 A가 "1번 칸부터 3번칸 까지 높이가 2만큼 늘어나도록 흙을 덮어!" 라고 했다고 가정해보자.

그럼, 1번 칸부터 3번칸 까지 +2씩 시켜주는 것이다. 그럼 다음과 같이 연병장의 높이가 변하게 될 것이다.

[ 3 , 4 , 5 , 4 , 5 ]

그리고 나서, 조교 B가 "1번칸부터 4번칸까지 높이가 1만큼 줄어들도록 흙을 파내!" 라고 했다고 가정해보자.

그럼, 1번 칸부터 4번칸 까지 -1씩 시켜주는 것이다. 그럼 다음과 같이 연병장의 높이가 변하게 될 것이다.

[ 2 , 3 , 4 , 4 , 5 ]

그리고 나서, 조교 C가 "2번칸부터 5번칸 까지 높이가 2만큼 늘어나도록 흙을 덮어!" 라고 했다고 가정해보자.

그럼, 2 ~ 5번칸을 + 2씩 시켜주는 것이다. 그럼 다음과 같이 연병장의 높이가 변하게 될 것이다.

[ 2 , 5 , 6 , 6 , 7 ]

이런식으로 문제를 해결할 수가 있다.

 

그런데 이렇게 해결했을 때, 큰 문제가 한 가지 있다. 최악의 경우를 생각해보자.

연병장의 크기 N이 최댓값인 100,000 이고, 조교의 수 M이 최댓값인 100,000 이고, 모든 100,000명의 조교가 내리는 지시가 모두 동일하게 [ 1 , 100000 , 1 ] 인 경우를 생각해보자.

즉, 100,000 명의 모든 조교가 "연병장의 1번칸부터 마지막 칸(100000번 칸) 까지 높이가 1만큼 늘어나도록 흙을 덮어!" 라고 지시를 한 것이다. 이 때, 위에서 이야기했던 간단한 접근 방법으로 계산을 하게 되면 다음과 같이 계산이 될 것이다.

연병장의 크기인 100,000 칸을 100,000번 방문해야 하기 때문에 총 100,000 * 100,000 만큼의 연산을 하게 된다.

그럼 10,000,000,000 만큼의 연산을 하게 된다. 말도 안되게 시간이 오래 걸린다는 것이다.

그래서 이 문제를 이와같이 매우 간단한 접근 방법으로 해결을 할 수는 없다.

 

#2. 누적합을 이용한 방법

그래서 이 문제를 "누적합" 을 이용한 방법으로 해결해 볼 것이다.

아까와 똑같은 배열을 다시한번 가져와보자.

[ 1 , 2 , 3 , 4 , 5 ]

이 때, "1번 칸부터 3번칸까지 + 2 만큼 하세요" 라고 한다면, 저 배열에서 바로 계산을 하는게 아니라, 새로운 배열에서 계산을 해줄 것이다. 그러기 위해서 먼저 모든 값이 0으로 초기화 되어 있는 새로운 배열을 하나 선언해보자.

[ 0 , 0 , 0 , 0 , 0 ]

그리고 "1번 칸부터 3번칸까지 + 2 만큼 하세요" 라는 명령을 수행하기 위해서 다음과 같이 연산을 진행해줄 것이다.

[ 2 , 0 , 0 , -2 , 0 ]

1번 칸에는 + 2를, 4번 칸에는 -2를 시켜준 것이다. 왜 갑자기 이런 계산을 했을까 ???

그 전에, 위의 상태에서 이 배열에서 앞에서부터의 누적값을 한번 구해보자. 구해보면 다음과 같을 것이다.

[ 2 , 2 , 2 , 0 , 0 ]

첫 번째 칸 = 이전의 칸이 없으므로 '2' 그대로 유지.

두 번째 칸 = 이전 칸 까지의 총합이 '2'였고, 두 번째 칸의 값이 '0'이였으므로 2 + 0 = '2'

세 번째 칸 = 이전 칸 까지의 총합이 '2'였고, 세 번째 칸의 값이 '0'이였으므로 2 + 0 = '2'

네 번째 칸 = 이전 칸 까지의 총합이 '2'였고, 네 번째 칸의 값이 '-2' 였으므로 2 + (-2) = '0'

다섯번째 칸 = 이전 칸 까지의 총합이 '0' 이였고, 다섯 번째 칸의 값이 '0'이였으므로 '0'.

위와 같이 계산이 되는 것이다.  그리고 원본의 배열인 [ 1 , 2 , 3 , 4 , 5 ] 와 [ 2 , 2 , 2 , 0 , 0 ]을 더하게 되면

[ 3 , 4 , 5 , 4 , 5 ] 와 같이 우리가 원했던 1번칸 ~ 3번칸만 +2가 된 결과를 얻을 수가 있다.

 

즉 ! "A번째 칸 부터 B번째 칸 까지 +a를 하세요" 라고 한다면, 우리는 새로운 배열에서

"A번째 칸에 +a를, B + 1번째 칸에 -a"를 한 후에, 이 배열에서의 누적합을 구하고, 원본 배열과 합쳐주기만 한다면 우리가 원하는 결과를 구할 수가 있다. 이렇게 값을 변경해야 하는 경우가 여러 번 있더라도 여러 번에 대해서 모두 계산해 준 후에, 최종적으로 누적합을 구한 후, 원본 배열과 합쳐주기만 하면 된다.

이렇게 계산을 하게 되면, 몇 개의 명령어가 몇 개의 범위에 대해서 주어지더라도, A 번째 칸에 +a, B + 1 번째 칸에 -a를 하고 이를 누적합을 구하기 위해서 더하기 위해서 N번 탐색, 그리고 원본 배열과 합치기 위해서 N번 탐색 만으로 해결할 수가 있다.

 

[ 소스코드 ]

#include <iostream>
 
#define MAX 100010
using namespace std;
 
struct cmd {
    int a;
    int b;
    int k;
};
 
int n, m;
int arr[MAX];
int accSum[MAX];
cmd cmdArr[MAX];
 
void input() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    for (int i = 0; i < m; i++) {
        int a, b, k; cin >> a >> b >> k;
        cmdArr[i] = { a - 1, b - 1, k };
    }
}
 
void solution() {
    for (int i = 0; i < m; i++) {
        int start = cmdArr[i].a;
        int end = cmdArr[i].b;
        int k = cmdArr[i].k;
        accSum[start] += k;
        accSum[end + 1] -= k;
    }
 
    for (int i = 0; i <= n; i++) {
        accSum[i + 1] += accSum[i];
    }
    for (int i = 0; i < n; i++) {
        arr[i] += accSum[i];
        cout << arr[i] << " ";
    }
    cout << endl;
 
}
 
void solve() {
    input();
    solution();
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("input.txt", "r", stdin);
    solve();
 
    return 0;
}