누적합 - 23829 인문예술탐사주간

GoRuth·2025년 6월 11일

algorithm

문제설명

이번 문제는

사진찍은 위치로부터의 나무 위치의 절댓값을 합친 값 => 사진 점수

주어진 위치의 사진 점수를 출력

을 해야하는 문제입니다.

접근법

0번 째 위치 : 1 + 3 + 7 + 9 + 10 = 30
- 현재 위치에서 나무까지의 거리입니다.
1번 째 위치 : 0 + 2 + 6 + 8 + 9 = 25
- 이전 위치에서 5개의 나무에 가까워졌기에, -5를 해주면 됩니다.
2번 째 위치 : 1 + 1 + 5 + 7 + 8 = 22
- 이전 위치에서 4개의 나무에 가까워졌고 1개의 나무와 멀어졌으니, -3 을 해주면 됩니다.

💡즉, 누적합을 통해 나무까지와의 거리를 구하면 됩니다!

내 위치 <= 🌲 : 이전 위치 - 1

내 위치 > 🌲 : 이전 위치 + 1

누적합 + 순차탐색 -> 실패

코드

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

public class Main {
  public static void main(String[] args) throws Exception {
    StringBuilder sb = new StringBuilder();
    BufferedReader br =
        new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st =
        new StringTokenizer(br.readLine());
    int size = Integer.parseInt(st.nextToken());
    int seq = Integer.parseInt(st.nextToken());
    List<Integer> list = new ArrayList<>();

    st = new StringTokenizer(br.readLine());
    for(int i = 0; i < size; i++) {
      list.add(Integer.parseInt(st.nextToken()));
    }
    list.sort((x, y) -> x - y);

    int min = list.get(0);
    int max = list.get(list.size() - 1);

    long[] dp = new long[max + 1];

    for(int a : list) {
      dp[min] += Math.abs(a - 1);
    }

    for(int i = min + 1; i < max + 1; i++) {
      int count = 0;
      for(int a : list) {
        if(a < i) {
          count++;
        } else {
          break;
        }
      }
      dp[i] = dp[i - 1] + count - (size - count);
    }

    for(int i = 0; i < seq; i++) {
      int idx = Integer.parseInt(br.readLine());

      if(idx < min) {
        sb.append(dp[min] + ((min - idx) * size)).append("\n");
      } else if(idx > max) {
        sb.append(dp[max] + ((idx - max) * size)).append("\n");
      } else {
        sb.append(dp[idx]).append("\n");
      }
    }

    System.out.println(sb);
  }
}

결과

이유

0번째부터 시작하기 때문에, 1번 탐색에 시간복잡도가 최대 O(N)으로 커짐
N과 Q은 최대 10^5까지 가능! 즉, 10^5 * 10^5 으로 2초내에 실행되는 게 불가능!

누적합 + 이분 탐색

코드

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

public class Main {
  public static void main(String[] args) throws Exception {
    StringBuilder sb = new StringBuilder();
    BufferedReader br =
        new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st =
        new StringTokenizer(br.readLine());
    int size = Integer.parseInt(st.nextToken());
    int seq = Integer.parseInt(st.nextToken());
    List<Integer> list = new ArrayList<>();

    st = new StringTokenizer(br.readLine());
    for(int i = 0; i < size; i++) {
      list.add(Integer.parseInt(st.nextToken()));
    }
    list.sort((x, y) -> x - y);

    int min = list.get(0);
    int max = list.get(list.size() - 1);

    long[] dp = new long[max + 1];

    for(int a : list) {
      dp[min] += Math.abs(a - min);
    }

    for(int i = min + 1; i < max + 1; i++) {
      int l = 0, r = list.size();
      while (l < r) {
        int mid = (l + r) / 2;
        if (list.get(mid) < i) {
          l = mid + 1;
        } else {
          r = mid;
        }
      }
      int count = l;

      dp[i] = dp[i - 1] + count - (size - count);
    }

    for(int i = 0; i < seq; i++) {
      int idx = Integer.parseInt(br.readLine());

      if(idx < min) {
        sb.append(dp[min] + ((long)(min - idx) * size)).append("\n");
      } else if(idx > max) {
        sb.append(dp[max] + ((long)(idx - max) * size)).append("\n");
      } else {
        sb.append(dp[idx]).append("\n");
      }
    }

    System.out.println(sb);
  }
}