백준 11660번 : 구간 합 구하기 5(Java)

🔗 문제 링크

11660번: 구간 합 구하기 5

---

📖 풀이 과정

 

- 누적합과 다이나믹 프로그래밍 유형의 문제입니다.
- 2차원 배열을 선언하여 입력 값을 할당합니다.
- dp 2차원 배열을 선언하여 각 행, 열마다의 값을 누적하여 더하여 계산합니다.
  - 이 때, dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + arr[i][j]의 식을 이용합니다.
- 또한, 누적합을 이용하여 해당하는 범위의 값을 계산하려면, dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1] 식을 이용해서 계산할 수 있습니다.
  - 이 때, 마지막에 값을 더하는 이유는 중복으로 제거되었기 때문입니다.

 

---

💻 코드

 

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

public class Main {
 static int[][] arr,dp;
 static int n,m;
 
 public static void main(String[] args) throws IOException {
  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  StringTokenizer st = new StringTokenizer(br.readLine()," ");
  n = Integer.parseInt(st.nextToken());
  m = Integer.parseInt(st.nextToken());
  arr = new int[n+1][n+1];
  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++){
    arr[i][j] = Integer.parseInt(st.nextToken());
   }
  }
  
  for(int i = 1; i< n+1; i++){
   for(int j = 1; j< n+1; j++){
    dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + arr[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(solve(x1,y1,x2,y2));
  }
 }
 
 private static int solve(int x1, int y1, int x2, int y2){
  return dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1];
 }
}