백준 19951 (태상이의 훈련소 생활) - java

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

 

문제

2020년 5월 14일 논산훈련소에 입대한 태상이는 첫 총기 훈련에서 가스 조절기를 잃어버리는 중대한 실수를 범했다. 그로 인해, 태상이는 조교들에게 눈총을 받게 되었다. 조교들은 태상이에게 연병장(운동장)의 흙을 옮기는 일을 주고 제대로 수행하지 못하면 징계를 내리려고 한다.

연병장은 일렬로 이어진 N개의 칸으로 이루어져 있으며 각 칸마다 높이를 가지고 있고, 첫 번째 칸부터 순서대로 1번, 2번, 3번, ..., N번 칸으로 명칭이 붙어있다. 조교들은 총 M명이 있으며, 각 조교들은 태상이에게 a번 칸부터 b번 칸까지 높이 k만큼 흙을 덮거나 파내라고 지시한다. 흙은 주변 산에서 얼마든지 구할 수 있으므로 절대로 부족하지 않다.

태상이는 각 조교의 지시를 각각 수행하면, 다른 조교의 지시로 흙을 덮어둔 칸을 다시 파내기도 하는 비효율적인 일이 발생하는 것을 깨달았다. 그래서 태상이는 각 조교의 지시를 모아 연병장 각 칸의 최종 높이를 미리 구해 한 번에 일을 수행하려고 한다.

불쌍한 태상이를 위해 조교들의 지시를 모두 수행한 뒤 연병장 각 칸의 높이를 구하자.

 

유형 : 누적합(Imos)

 

접근 방식

• 쿼리 형태로 지속적으로 누적합을 반영해야 하는 문제이다.
• 해당 문제에서 특정 구간을 지속해서 반복적으로 누적합한다면 시간 초과가 발생할 것이다.
• Imos를 통해 마지막에 한번의 누적합 연산으로 정답을 구하도록 하자
• 배열의 크기를 1더 크게 잡는 것도 중요하다. Imos : (b[s] + v , b[e+1] - v)이기 때문이다.

코드

import java.util.*;
import java.io.*;

public class BOJ_19951_태상이의_훈련소_생활 {

    static int n,m;
    static int[] arr;
    static int[] sum;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        arr = new int[n+2];
        sum = new int[n+2];

        st = new StringTokenizer(br.readLine()," ");
        for(int i = 1 ; i <= n ; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        for(int i = 1 ; i <= m ; i++) {
            st = new StringTokenizer(br.readLine()," ");

            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            sum[s] += v;
            sum[e + 1] -= v;
        }

        for(int i = 1 ; i <= n + 1 ; i++) {
            sum[i] += sum[i-1];
        }

        StringBuilder sb = new StringBuilder();

        for(int i = 1 ; i <= n ; i++) {
            arr[i] += sum[i];
            sb.append(arr[i]+" ");
        }
        System.out.println(sb);

        br.close();
    }
}