© 2025 anveloper.dev
GitHub·LinkedIn·Contact

목차

  • 문제
  • 입력
  • 출력
  • 예제
  • 풀이
  • 코드
  • 복잡도
풀이 목록으로 돌아가기

BOJ 21672 - Ханты-Мансийск – Париж

2023-04-05
BOJ
Unrated
java
원본 문제 보기
구현

문제

BOJ 21672 - Ханты-Мансийск – Париж

N×M 크기의 2차원 배열이 주어질 때, K개의 구간 합 쿼리에 답하라. 각 쿼리는 (i, j)부터 (x, y)까지의 부분 행렬 합을 구한다.

입력

첫째 줄에 N, M, 이후 N줄에 배열, K개의 쿼리가 주어진다.

출력

각 쿼리에 대해 부분 행렬의 합을 출력한다.

예제

입력출력
3 3 1 2 3 4 5 6 7 8 9 2 1 1 2 2 1 1 3 312 45

풀이

행별 누적합(prefix sum)을 전처리한 뒤, 각 쿼리에서 행 범위를 순회하며 열 구간 합을 계산한다.

  1. 입력과 동시에 각 행의 누적합 dp[i][j] = arr[i][1] + ... + arr[i][j]를 구한다
  2. 각 쿼리 (i, j, x, y)에서 행 i부터 x까지 순회하며 dp[row][y] - dp[row][j-1]을 합산한다

핵심 아이디어: 행별 누적합을 사용하면 열 방향 구간 합을 O(1)에 구할 수 있어 쿼리당 O(행 수)로 처리된다.

코드

package day449;
 
import java.io.*;
import java.util.*;
 
public class Day423BOJ21672차원배열의합 {
  static int N, M, K;
  static int[] sum;
  static int[][] arr, dp;
 
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
    StringTokenizer st = new StringTokenizer(br.readLine());
 
    N = Integer.parseInt(st.nextToken());
    M = Integer.parseInt(st.nextToken());
    arr = new int[N + 1][M + 1];
    dp = new int[N + 1][M + 1];
 
    for (int i = 1; i <= N; i++) {
      st = new StringTokenizer(br.readLine());
      for (int j = 1; j <= M; j++) {
        arr[i][j] = Integer.parseInt(st.nextToken());
        dp[i][j] = arr[i][j] + dp[i][j - 1];
      }
    }
 
    K = Integer.parseInt(br.readLine());
    sum = new int[K];
 
    for (int t = 0; t < K; t++) {
      st = new StringTokenizer(br.readLine());
      int i = Integer.parseInt(st.nextToken());
      int j = Integer.parseInt(st.nextToken());
      int x = Integer.parseInt(st.nextToken());
      int y = Integer.parseInt(st.nextToken());
 
      for (int row = i; row <= x; row++) {
        sum[t] += dp[row][y] - dp[row][j - 1];
      }
      sb.append(sum[t]).append("\n");
    }
 
    System.out.println(sb);
    br.close();
  }
}

복잡도

  • 시간: O(NM + KN) - 전처리 + 쿼리 처리
  • 공간: O(N*M)