링크

11660 구간 합 구하기 5

문제

풀이

처음에 dp로 해결했는데도 시간초과가 나서 블로그를 봤따.
System.out.println으로 출력했었는데 StringBuilder로 바꿔보니 해결완료

위 사진을 보면 dp에다가 누적으로 계속 쌓아주면 된다.
위 사진 dp 기준으로 첫번째 줄이
1 3 6 10 이면 2에서 시작해서 4까지 합을 구한다고 하면
4번째값인 10에다가 1번째값인 1을 빼주면 9가 나온다.
이런식으로 계산하면 된다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

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

        String[] arr = br.readLine().split(" ");
        int n = Integer.parseInt(arr[0]);
        int m = Integer.parseInt(arr[1]);

        int[][] map = new int[n][n];
        int[][] dp = new int[n][n];

        for(int i=0;i<n;i++){
            arr = br.readLine().split(" ");

            int sum = 0;
            for(int j=0;j<arr.length;j++){
                map[i][j] = Integer.parseInt(arr[j]);
                sum += map[i][j];
                dp[i][j] = sum;
            }

        }

//        for(int i=0;i<dp.length;i++){
//            System.out.println(Arrays.toString(map[i]));
//        }
//
//        System.out.println("-------------------------");
//
//        for(int j=0;j<dp.length;j++){
//            System.out.println(Arrays.toString(dp[j]));
//        }

        for(int i=0;i<m;i++){
            arr = br.readLine().split(" ");

            int startX = Integer.parseInt(arr[0]) - 1;
            int startY = Integer.parseInt(arr[1]) - 1;
            int endX = Integer.parseInt(arr[2]) - 1;
            int endY = Integer.parseInt(arr[3]) - 1;

            int result = 0;
            for(int j=startX;j<=endX;j++){

                if(startY == 0){
                    result += dp[j][endY];
                } else{
                    result += dp[j][endY] - dp[j][startY-1];
                }
//                System.out.println(result);

            }
            sb.append(result + "\n");
//            System.out.println(result);

        }


        System.out.println(sb.toString());


    }


}