📝문제

다른 dp문제들보다 쉽게 풀 수 있었다. 점화식 생각해내는 것이 쉬웠던 거 같다.
내가 문제를 풀면서 주의했던 것은 m이 최대 100000이 될 수 있었던 것!
그렇다면 계산을 최대 100000번 해야된다는 것인데, 그 계산 과정에서 반복문을 거친다면
시간초과를 피할 수 없을 것이라는 예감이 들었다.
그래서 입력을 받는 동시에 누적합을 dp 배열에 저장하고,
구해야 할 범위가 주어졌을 때 해당 범위의 누적합만 구하도록 했다.

📌코드

package Baekjoon;

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

public class BOJ11660 {
  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());
    /**
     * dp[i][j]에는 (0,0)에서부터 (i,j)까지 더한 값을 넣는다
     * dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + map[i][j]
     */

    int[][] map = new int[n+1][n+1];
    int[][] dp = new int[n+1][n+1];
    for (int i = 1; i < n+1; i++) {
      st = new StringTokenizer(br.readLine());
      for (int j = 1; j < n+1; j++) {
        map[i][j] = Integer.parseInt(st.nextToken());
        dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + map[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());
      System.out.println(dp[x2][y2]-dp[x2][y1-1]-dp[x1-1][y2]+dp[x1-1][y1-1]);
    }
  }
}