[JAVA] 백준 11660: 구간 합 구하기 5

문제

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

풀이

package Baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class S1_11660 {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    StringBuilder sb = new StringBuilder();

    //n, m 입력
    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());

    ArrayList<int[]> sumList = new ArrayList<>();
    int[] sum;

    //행렬 입력
    int[][] matrix = new int[n][n];

    for (int i = 0; i < n; i++) {
      st = new StringTokenizer(br.readLine());
      for (int j = 0; j < n; j++) {
        matrix[i][j] = Integer.parseInt(st.nextToken());
      }
    }

    for (int[] arr : matrix) {
      //합배열 만들기
      sum = new int[n+1];
      for (int i = 1; i <= n; i++) {
        sum[i] = sum[i-1] + arr[i-1];
      }
      sumList.add(sum);
    }

    //구해야하는 합배열
    for (int i = 0; i < m; i++) {
      st = new StringTokenizer(br.readLine());
      int x1 = Integer.parseInt(st.nextToken());
      int y1 = Integer.parseInt(st.nextToken());
      int x2 = Integer.parseInt(st.nextToken());
      int y2 = Integer.parseInt(st.nextToken());
      int result = 0;

      for (int x = x1-1; x <= x2-1; x++) {
        int[] rowSum = sumList.get(x);
        result += rowSum[y2] - rowSum[y1-1];
      }
      sb.append(result + "\n");
    }
    System.out.print(sb);

  }
}

시간 초과가 떠서 아예 알고리즘을 수정했다.
2차원 배열에서 행 별로 합 배열을 만들고, 입력 인덱스만큼의 값만 누적해서 result에 더하고 출력했다.

---

시간 초과 풀이

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

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    StringBuilder sb = new StringBuilder();

    //n, m 입력
    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());

    //행렬 입력
    String[][] matrix = new String[n][n];

    for (int i = 0; i < n; i++) {
      matrix[i] = br.readLine().split(" ");
    }

    //질의 입력
    for (int i = 0; i < m; i++) {
      st = new StringTokenizer(br.readLine());
      int x1 = Integer.parseInt(st.nextToken()) - 1;
      int y1 = Integer.parseInt(st.nextToken()) - 1;
      int x2 = Integer.parseInt(st.nextToken()) - 1;
      int y2 = Integer.parseInt(st.nextToken()) - 1;
      int sum = 0;

      for (int x = x1; x <= x2; x++) {
        for (int y = y1; y <= y2; y++) {
          sum += Integer.parseInt(matrix[x][y]);
        }
      }
      sb.append(sum + "\n");
    }
    System.out.print(sb);
  }
}

---

[Do it! 알고리즘 코딩테스트 자바편]

과정

1. 문제 분석 & 풀어보기
질의 개수가 100,000이므로 질의마다 합을 구하면 안되고, 구간 합 배열을 이용해야 한다.

2차원 구간 합 배열 D[X][Y] 정의

D[X][Y] = 원본 배열의 (0,0)부터 (X,Y)까지의 사각형 영역 안에 있는 수의 합

D[i][j]의 값을 채우는 구간 합 공식

D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j]

질의 X1, Y1, X2, Y2에 대한 답을 구간 합으로 구하는 방법

D[X2][Y2] - D[X1-1][Y2] - D[X2][Y1-1] + D[X1-1][Y1-1]

2. 슈도코드

3. 코드

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

    int N = Integer.parseInt(st.nextToken());
    int M = Integer.parseInt(st.nextToken());

    int A[][] = new int[N+1][N+1];
    for (int i = 0; i < N; i++) {
      st = new StringTokenizer(br.readLine());
      for (int j = 0; j < N; j++) {
        A[i][j] = Integer.parseInt(st.nextToken());
      }
    }
    
    int D[][] = new int[N+1][N+1];
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j];
      }
    }
    
    for (int i = 0; i < m; i++) {
      st = new StringTokenizer(br.readLine());
      int x1 = Integer.parseInt(st.nextToken());
      int y1 = Integer.parseInt(st.nextToken());
      int x2 = Integer.parseInt(st.nextToken());
      int y2 = Integer.parseInt(st.nextToken());
      
      int result = D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1]
      System.out.println(result);
      
  	}
  }
}
    

사실 공식 부분 제대로 이해못했다. ㅎ헤헤