JAVA 백준 19951 태상이의 훈련소 생활 (누적합)

 

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

 

---

문제

1. 첫째 줄에 연병장의 크기 N와 조교의 수 M ( 1 <= N, M <= 10000 ) 이 입력된다.
2. 둘째 줄에 연병장 각 칸의 높이 ( -10000 <= 높이 <= 10000 ) N개가 공백으로 구분되어 입력된다.
3. 셋째 줄부터 M개의 줄에 조교의 지시 a, b, k  ( 1 <= a <= b <= N, | k | <= 100 )  가 공백으로 구분되어 입력된다.
4. k가 0 또는 양수인 경우 a번 칸부터 b번 칸까지 | k | 만큼 증가시킨다.
5. k가 0보다 작을 경우 a번 칸부터 b번 칸까지 | k | 만큼 감소시킨다.

---

 

 

왜 맞았지 싶은 정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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[] high = new int[N];

        for (int i = 0; i < N; i++) {
            high[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());

            if (k >= 0) {
                for (int j = a - 1; j < b; j++) {
                    high[j] += k;
                }
            } else {
                for (int j = a - 1; j < b; j++) {
                    high[j] += k;
                }
            }
        }


        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < N; i++) {
            sb.append(high[i]).append(" ");
        }

        System.out.println(sb);
    }
}

 

다른 사람들 시간의 몇 배는 되는데 왜 이걸 맞았다고 해준 건지 모르겠다.

시간 초과 설정이 안 된 건가 싶다.

좀 그러니까 다른 방법으로 문제를 풀어보겠다.

 

 

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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[] high = new int[N];

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

        int[] orders = new int[N + 1];
        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());

            orders[a - 1] += k;
            orders[b] -= k;
        }


        StringBuilder sb = new StringBuilder();
        int num = 0;

        for (int i = 0; i < N; i++) {
            num += orders[i];
            sb.append(high[i] + num).append(" ");
        }

        System.out.println(sb);
    }
}

 

 

조교의 지시를 누적합 배열에 저장하여 지시를 모두 저장한 배열을 만든다.

이 배열을 이용하여 연병장 각 칸의 값을 구해 결과를 구할 수 있다.

 

조교의 지시를 저장할 때 범위를 신경써야 된다.

a부터 b까지 k값을 더해야 되는데 이 때 a에서 b까지 모두 포함해야 된다는 점을 유의하여 범위 지정을 해야 된다.

a에서 b가 모두 포함되어야 하므로 b에도 k가 적용되어야 되므로 포함하여 범위를 정하면 된다.