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

문제

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

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

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

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

 

입력

첫 줄에 연병장의 크기 N과 조교의 수 M이 주어진다.

둘째 줄에 연병장 각 칸의 높이 Hi가 순서대로 N개 주어진다.

셋째 줄부터 M개의 줄에 각 조교의 지시가 주어진다.

각 조교의 지시는 세 개의 정수 a, b, k로 이루어져 있다.

• k ≥ 0인 경우 a번 칸부터 b번 칸까지 높이가 각각 |k| 만큼 늘어나도록 흙을 덮어야 한다.
• k < 0인 경우 a번 칸부터 b번 칸까지 높이가 각각 |k| 만큼 줄어들도록 흙을 파내야 한다.

 

출력

모든 지시를 수행한 뒤 연병장 각 칸의 높이를 공백을 사이에 두고 출력한다.

 

구현

하나하나 다 계산해주면 당연하게도 시간초과가 난다..

그렇다면 저 지시들을 한번에 계산해서 원래의 배열에 더해줘야 하는데 쉽게 계산하는 방법이 없나? 하다가 누적합을 사용하게 됐다.

sums라는 배열을 하나 더 만들어서 지시의 처음과 끝, 즉 a와 b에 k만큼의 값을 저장해준다.

sums[a]에는 k를 더하고, b+1부터는 k만큼 연산을 하지 않아도 되니까 -k를 더해준다.

그렇게 예제 입력에 나온

1 5 -3
6 10 5
2 7 2

를 계산하면 다음과 같이 나온다.

1	2	3	4	5	6	7	8	9	10
-3	2	0	0	0	8	0	-2	0	0

지시에 맞게 모두 더해주고 sums의 처음부터 계산을 해주는데, 이때 sums[i] = sums[i-1]+sums[i]가 된다.

1	2	3	4	5	6	7	8	9	10
-3	-1	-1	-1	-1	7	7	5	5	5

그렇게 계산한 배열을 원래의 배열에 더해주면 끝

 

코드

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

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

        int N = Integer.parseInt(st.nextToken());   // 연병장 크기
        int M = Integer.parseInt(st.nextToken());   // 조교의 수

        st = new StringTokenizer(br.readLine());
        int[] arr = new int[N + 1];
        int[] sums = new int[N + 2];

        for (int i = 1; i < N + 1; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < M; i++) {    // 지시
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());

            // 처음과 끝만 계산해서 누적합으로 처리
            sums[a] += k;
            sums[b + 1] -= k;
        }

        for (int i = 1; i < N + 1; i++) {   // 누적합 계산
            sums[i] = sums[i - 1] + sums[i];
        }

        for (int i = 1; i < N + 1; i++) {
            System.out.print(arr[i] + sums[i] + " ");
        }
    }
}

 

 

문제 출처

https://www.acmicpc.net/submit/19951/97010348