19951번 태상이의 훈련소 생활

※ 이 문제는 1차원 배열에 대한 문제이고, 2차원 배열로 확장시킨 문제가

2021년 9월 11일 토요일 2022 카카오 블라인드 코딩테스트 6번에 출제됐다.

 

※ 이 글은 안즈님의 카카오 6번 문제 해설(누적합을 이용한 연산)을 참고하여 작성하였고,

제가 다시 편히 보기 위해 정리하였습니다.

 

 

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

 

배열이 주어지고, 배열의 구간에 수를 더하고 빼는 쿼리가 있다.

세그먼트 트리를 이용해도 되지만, 우리는 연산 중간에 배열의 값을 알 필요가 없고,

 

모든 쿼리(연산) 이후에 마지막 단 한 번만 구하면 되기 때문에,

 

누적합을 이용할 수 있다.

 

문제에 대한 정답 코드는 맨 아래에 있다.

 

이 문제를 풀기 위한 누적합 연산 개념 설명(아래 사진)을 추가한다.

 

 

 

 

 

 

 

 

H : 누적합

 

#include <bits/stdc++.h>

using namespace std;

#define MAX 100100

int N; // 연병장의 수
int M; // 조교의 수
int sum[MAX], arr[MAX], H[MAX];
// 누적합 배열, 연병장 높이 배열

int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\lazy_bronze\\2.in", "r", stdin);
    cin.tie(0);

    scanf("%d %d", &N, &M);
    
    // 연병장 각 칸의 높이
    for (int i = 1; i <= N; i++) {
        scanf("%d", &H[i]);
    }

    int a = 0, b = 0, k = 0;
    // 조교의 지시
    for (int i = 0; i < M; i++) {
        scanf("%d %d %d", &a, &b, &k);
        arr[a] += k;
        arr[b + 1] += -k;
    }

    for (int i = 1; i <= N; i++) {
        sum[i] = sum[i - 1] + arr[i];
        //printf("sum[%d] = %d\n", i, sum[i]);
    }

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

    printf("\n");

    return 0;
}