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

문제

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

풀이 방법

처음엔 문제를 쉽게 생각해서 1차원 배열에 연병장 높이들을 넣은 뒤 각 작업마다 연산을 해주려고 했다. 그런데 문제 조건을 보면 N과 M이 최대 100,000이기 때문에 1초를 초과한다.
M은 작업의 수라서 무조건 반복해야하기 때문에 N을 줄이는 방식을 택해야한다.
바로 누적합이다.

1. 연병장 배열과 누적합 배열 입력 받기

먼저 연병장 높이들을 받기 위해 1차원 배열을 생성하여 연병장 높이들을 받아준다. 이후 누적합 배열에 시작과 끝을 입력 받는다.
이 때 주의해야하는 점이 우리는 누적합을 추후에 계산할 것이기 때문에 예를 들어 1 ~ 5까지 4만큼 더하기 위해서는 누적합 배열의 1번 인덱스에 4를 더해주어야한다. 또한 6번 인덱스에 4를 빼주어야한다. 누적합 배열을 순회하면서 이전 인덱스의 값을 현재 인덱스의 값에 더해줄 것이기 때문에 이런 방식으로 값을 주어야한다.

2. 누적합 적용하기

누적합 배열은 1번에서 완성되었으므로 누적합 배열을 돌면서 이전 인덱스의 값을 현재 인덱스에 더해준다.

3. 출력하기

마지막으로 누적합 배열에서 각 인덱스에 해당하는 값들을 공백으로 나누어 출력하면 된다.

정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class p19951 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(st.nextToken()); // 연병장 길이
        int M = Integer.parseInt(st.nextToken()); // 작업 개수

        int[] arr = new int[N+1]; // 연병장 배열
        int[] sum = new int[N+1]; // 누적합 배열

        st = new StringTokenizer(br.readLine());

        // 연병장 입력 받기
        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 start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            sum[start] += weight;
            if (end + 1 <= N) {
                sum[end + 1] -= weight;
            }
        }

        // 누적합 적용하기
        for(int i=1; i<=N; i++) {
            sum[i] += sum[i-1];
            sb.append((arr[i] + sum[i])).append(" ");
        }


        bw.write(sb.toString().trim()); // 마지막 공백 제거
        bw.flush();
        bw.close();
    }
}