[백준] java - 11660 구간 합 구하기 5

문제가 단순해서 누적합으로 풀어도 될 것 같지만 시간제한이 있기 때문에 DP로 접근해야 합니다.

세로 열에 대한 누적합을 dp에 먼저 저장 후
(시작행-1) - 끝 행을 빼주면되는 단순한 구조입니다.

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int map[][];
    static long dp[][];
    public static void main(String[] args) throws IOException {
    //시간 줄이기 위한 sb
        StringBuilder sb = new StringBuilder();
        //입력받기
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        map = new int[n+1][n+1];
        dp = new long[n+1][n+1];
        for(int i=1; i<=n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=n; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        //map입력 받기 완료
        //1행 초기화
        for (int i = 1; i <= n; i++) {
            dp[1][i] = map[1][i];
        }
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                    dp[i][j] = dp[i-1][j] + map[i][j];
            }
        }
        //각 열에 대한 누적값 저장
        
        for(int k=0; k<m; k++) {
            st = new StringTokenizer(br.readLine());
            int sx = Integer.parseInt(st.nextToken());
            int sy = Integer.parseInt(st.nextToken());
            int ex = Integer.parseInt(st.nextToken());
            int ey = Integer.parseInt(st.nextToken());
            long sum = 0;
            for(int i=sy; i<=ey; i++){
                sum += dp[ex][i] - dp[sx-1][i];
            }
            //시작열부터 끝 열까지 누적값 더하기
            sb.append(sum).append("\n");

        }
        System.out.println(sb);

    }
}