[백준] 11660번 : 구간 합 구하기 5[Java]

#풀이

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



public class Main {


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[][] matrix = new int[1025][1025];
        int[][] dp = new int[1025][1025];
        for(int i = 1; i<=N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j<=N; j++){
                matrix[i][j] = Integer.parseInt(st.nextToken());
                dp[i][j] = matrix[i][j]+dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1];
            }
        }

        int y1,y2,x1,x2;
        for(int i = 0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            y1 = Integer.parseInt(st.nextToken());
            x1 = Integer.parseInt(st.nextToken());
            y2 = Integer.parseInt(st.nextToken());
            x2 = Integer.parseInt(st.nextToken());
            bw.write(dp[y2][x2]+dp[y1-1][x1-1]-dp[y2][x1-1]-dp[y1-1][x2]+"\n");
        }
        bw.flush();
    }
}

#성능

#정리

처음 풀때는 일일이 다 탐색해서 더하는 방법으로 하여 시간초과가 났다.

이 경우, 최대 맵 크기(NxN) 내에서 모두 탐색하면서 연산 횟수(M) 만큼 계산하게 되면 1,024 x 1,024 x 100,000(최악의 경우) 으로 문제를 풀지 못하게 된다. 

따라서 나는 DP로 해당문제를 풀었다.

 

// dp[i][j] = (1,1)부터 (i,j)까지의 누적합

 

DP의 점화식은 다음과 같다.

dp[i][j] = matrix[i][j] 
           + dp[i-1][j]    // 위쪽 영역
           + dp[i][j-1]    // 왼쪽 영역
           - dp[i-1][j-1]; // 중복된 왼쪽 위 영역 제거

 

부분합 계산식은 다음과 같다.

sum = dp[y2][x2]
      - dp[y1-1][x2]
      - dp[y2][x1-1]
      + dp[y1-1][x1-1];