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

 

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

 

1. 서론

 

이 문제는 누적합 유형의 문제이다. 그런데 문제는 일반적으로 누적해서 합을 구한 후 그를 응용하는 일반적인 누적합 문제가 아니다.

나는 GPT에게 이 문제를 어떻게 누적합으로 푸는 거냐고 물어봤고 GPT는 '차분배열'을 이용하면 된다고 했다.

아마... 혼자서는 못 풀었을 듯. 이렇게 하나 배웠으니 뿌듯합니다.

 

 

반응형

 

2. 문제 풀이

 

n개의 칸이 있고, 특정 구간을 뜻하는 a, b가 m번 주어진다. n개의 칸에서 a~b 구간만 k만큼 값을 더해준 값을 구하는 것이 문제다.

문제는 이 n, m의 범위가 100,000 이라는 것이다. 즉, 그냥 단순히 반복문을 이용해 구간만큼 값을 돌려준다면 시간초과가 나게 되는 문제인 것이다.

 

처음에는 문제를 보고 DP 아니면 이분탐색일 것 같은데 도저히 어떻게 풀어야 할지 생각이 안났다. (원래 그 두 유형에 약하므로)

그래서 문제 유형을 봤는데 누적합... 구간합을 이용한 문제만 풀어봐서 더더욱 풀이를 모르겠더라는... 그래서 GPT에게 어떻게 이 문제를 누적합으로 푸냐고 물어봤다.

 

차분 배열(Difference Array)은 배열 값간의 차를 저장하는 방식이다.

예를 들어 1,2,3,4,5 라는 배열이 있다면 배열에 각 근접 배열의 차인 1,1,1,1,1을 저장하는 방식이다.

이를 활용하면 구간의 업데이트가 많은 경우, 카운팅이나 계산을 효율적으로 해야 하는 경우, 시간복잡도를 줄여야 하는 경우에 활용할 수 있다.

 

만약 위의 배열에서 2~4 구간에 3을 다 더해준다고 가정하면

1,5,6,7,5가 된다. 즉 1,4,1,1,-2가 되는 것이다.

배열의 첫 번째 값과 두 번째 값 사이에 +3만큼 더 차이가 나게 되고, 4와 5값은 -3만큼 차이가 더 나게 되므로 이 두 가지 값만 저장해 주면 되는 것이다.

 

3. 코드 설명

 

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

public class Main {

  static int n, m;
  static int[] a;

  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());

    a = new int[n];
    int[] diff = new int[n + 1];
    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < n; i++) {
      a[i] = Integer.parseInt(st.nextToken());
      if (i > 0)
        diff[i] = a[i] - a[i - 1];
      else
        diff[i] = a[i];
    }

    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 x = Integer.parseInt(st.nextToken());

      diff[a - 1] += x;
      if (b < n)
        diff[b] -= x;
    }

    a[0] = diff[0];
    for (int i = 1; i < n; i++)
      a[i] = a[i - 1] + diff[i];

    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < n; i++)
      sb.append(a[i] + " ");
    
    System.out.print(sb.toString());
  }
}

 

 

diff라는 차분 배열을 만들어 값을 입력받는 동시에 저장해줬다.

그리고 위에서 말한 것처럼 구간의 시작점에서 x값을 더하고, 끝점에서 x값을 빼줬다. (그만큼 구간의 차가 벌어졌기 때문에)

그럼 구간간의 차가 누적되어 계산된다.

이를 배열의 첫 번째 값부터 구간의 차를 더해 값을 구한다.

 

이때 의외의 복병이 배열을 전부 다 출력하다 보니 시간이 오래 걸려서 StringBuilder로 바꿨더니 시간이 반으로 줄었다.

항상 java를 사용하면 주의해야 할 점.... (근데 어차피 코테보면 다 프로그래머스라 웬만하면 출력할 일이 없긴 하다...)