2167 2차원 배열의 합 ⬛

📋문제 정리

• 2차원 배열이 주어졌을때 ( i , j ) 부터 ( x , y )의 합을 구하라.

🎯풀이

• 브루트 포스로 배열을 돌면서 풀면 되는거 같지만 주어진 범위를 보면 시간 초과가 난다.
• 2차원 배열의 누적 합으로 문제를 풀면 된다.
• 2차원 배열을 입력받아 누적 합 배열을 만든다.
• 좌표들을 입력 받아 구간의 합을 구하고 출력한다.

누적 합 : prefixSum[i][j] = arr[i-1][j-1] + prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1];

배열 값 + 왼쪽 누적합 + 위쪽 누적합 - 교집합 누적합

합 연산 : prefixSum[x][y] - prefixSum[x][j-1] - prefixSum[i-1][y] + prefixSum[i-1][j-1];

전체 누적합 - 왼쪽 누적합 - 위쪽 누적합 + 교집합 누적합

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;

public class Main {

  static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  static StringTokenizer st;
  static StringBuilder sb =  new StringBuilder();

  public static void main(String[] args) throws IOException {
    st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());
    int arr[][] = new int[n][m];
    int ps[][] = new int[n+1][m+1]; //누적 합 2차원 배열 +1 필수 [0]이 들어간 가로나 세로는 전부 0으로 만듬
    
    for(int i=0;i<n;i++){
      st = new StringTokenizer(br.readLine());
      for(int l=0;l<m;l++){
        arr[i][l] = Integer.parseInt(st.nextToken());
      }
    }

    for(int i=1;i<=n;i++){
      for(int l=1;l<=m;l++){
        ps[i][l] = arr[i-1][l-1] + ps[i-1][l] + ps[i][l-1] - ps[i-1][l-1]; // 누적 합 배열 초기화
      }
    }

    int k = Integer.parseInt(br.readLine());

    for(int l=0;l<k;l++){
      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());

      sb.append((ps[x][y] - ps[i-1][y] - ps[x][j-1] + ps[i-1][j-1])+"\n"); // 합 연산
    }

    System.out.println(sb);
    br.close();
  }
}