[백준 11951번] 태상이의 훈련소 생활

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

19951번: 태상이의 훈련소 생활

 

접근 과정
1. 어떤 문제로 이해 했는가? 그리고 문제의 제약 조건은?

연병장의 흙을 조교의 지시에 맞게 옮기는 작업을 한다.

N개의 칸으로 이루어져있고, 각 칸마다 높이가 주어지는데

조교 M명이 i~j칸을 높이 k만큼 덮거나 파내라고 지시한다.

 

작업을 하기 전 최종 높이를 미리 구해보자

 

 

2. 나의 방식대로 문제를 재정의 하자.

N칸의 각 높이가 주어지고, 파내거나 덮는 k값을 연속해서 +,-한다는 점을 생각해야한다.

+-값을 미리 계산해 따로 저장해두고, 연산을 한번에 한다면 효율적일 것이다.

 

 

3. 어떤 알고리즘과 자료구조를 사용할 것인가?

누적합 개념을 활용한다.

기존 칸의 높이를 더하는게 아니라, 새롭게 추가되는 값이 i~j칸에서 연속한다는 점을 이용해서

ary[i]에서 k를 더하고, 연산이 끝난 지점인 ary[j+1]에서 k를 빼준다.

ary[i]	값	누적값
ary[0]	0	0
ary[1]	k	k
ary[2]	0	k
ary[3]	-k	0
ary[4]	0	0

 

4. 어떻게 계산할 것인가?

1) 입력

BufferedReader

 

 

2) 시간 복잡도 계산

O(n)

 

 

5. 주의할 점은 무엇인가?

누적합 개념에 주의

 

6. 풀이 과정

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

public class q19951 {

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

    StringTokenizer st = new StringTokenizer(br.readLine());
    Integer N = Integer.parseInt(st.nextToken());
    Integer M = Integer.parseInt(st.nextToken());

    Integer[] result = new Integer[N+1];

    st = new StringTokenizer(br.readLine());
    for (int i = 1; i <= N; i++) {
      result[i] = Integer.parseInt(st.nextToken());
    }
    
    int[] addSum = new int[N + 2];
    addSum[0] = 0;
    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 swap = Integer.parseInt(st.nextToken());

      addSum[start] += swap;
      addSum[end + 1] -= swap;
    }

    int add = 0;
    for (int j = 1; j <= N; j++) {
      add += addSum[j];
      result[j] += add;
      System.out.print(result[j] + " ");
    }
    System.out.println("");

    br.close();
  }

}

 

7. 개선점

누적합이 어떻게 응용될 수 있을지 고려해보기