[백준] 2167 2차원 배열의 합

문제보기

DP 로 해도 되고 부분합 써도 되는데, 나는 부분합으로 풀었음

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

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());
    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());
    int[][] map = new int[n][m];
    for(int i = 0 ; i < n ; i++){
      st = new StringTokenizer(br.readLine());
      for(int j = 0 ; j < m ; j++){
        map[i][j] = Integer.parseInt(st.nextToken());
      }
    }
		
    // 부분합을 저장할 변수
    // 0,0부터, i,j까지의 합을 저장한다
    int[][] psum = new int[n][m];
    // 첫 칸은 당연히 자기가 부분합의 전부임
    psum[0][0] = map[0][0];
    // 행과 열이 0인 경우에 대해 따로 구해준다
    for(int i = 1 ; i < m ; i++ ){
      psum[0][i] = psum[0][i-1] + map[0][i];
    }
    for(int i = 1 ; i < n ; i++ ){
      psum[i][0] = psum[i-1][0] + map[i][0];
    }

    // 행과 열이 1 이상인 경우에는 이렇게 구해주면 된다
    for(int i = 1 ; i < n ; i++){
      for(int j = 1 ; j < m ; j++){
        psum[i][j] = psum[i-1][j] + psum[i][j-1] - psum[i-1][j-1] + map[i][j];
      }
    }


    int k = Integer.parseInt(br.readLine());
    StringBuilder sb = new StringBuilder();
    
    while(k-->0){
      st = new StringTokenizer(br.readLine());
      int i = Integer.parseInt(st.nextToken())-1;
      int j = Integer.parseInt(st.nextToken())-1;
      int x = Integer.parseInt(st.nextToken())-1;
      int y = Integer.parseInt(st.nextToken())-1;
			
      // 기본적으로 i,j부터 x,y 까지의 합은
      // (0,0)부터 (x,y)까지의 합에서
      // (0,0)부터 (i-1,y)까지의 합을 빼주고
      // (0,0)부터 (x, j-1)까지의 합을 빼주고
      // (0,0)부터 (i-1, j-1)은 두번 빠졌으니까 한번 더해준다
      // 다만 인덱스 에러 때문에 아래처럼 나눠서 계산한것 뿐이다..
      int temp = psum[x][y];
      if( i-1 >= 0){
        temp -= psum[i-1][y];
      }
      if( j-1 >= 0){
        temp -= psum[x][j-1];
      }
      if( i-1 >= 0 && j-1 >= 0){
        temp += psum[i-1][j-1];
      }
      sb.append(temp + "\n");
    }
    System.out.println(sb);


  }
}