구간 합 구하기 5

https://www.acmicpc.net/problem/11660

풀이

(x1, y1) 부터 (x2,y2)까지의 구역의 합을 구하는 문제로 dp로 풀이할 수 있다.

구역 합을 구해야하는데 이때 구역합을 구하기 위한 점화식을 구하는 것에 조금 어려움이 있었다.

우선 dp를 초기화해야는데 초기화를 할 때

1,1에서 x,y 까지의 합을 기억해 둔다.

점화식은

dp[x][y] = dp[x - 1][y] + dp[x][y - 1] - dp[x - 1][y - 1] + arr[x][y]

와 같다.

이렇게 되는 이유는 1,1에서 x,y까지의 구간을 사각형으로 생각해보면 dp[x - 1][y]과 dp[x][y-1]은 x,y 바로 전까지의 구간 합이고 dp[x-1][y-1]이 중복되어 더해지기 때문에 한 번 빼준다.

(x1,y1) 부터 (x2,y2)까지의 합은

위의 점화식을 응용해서

dp[x1 - 1][y2] + dp[x2][y1 - 1] - dp[x1 - 1][y1 - 1]

와 같다.

코드

import java.io.*;

public class Main {
    static int[] dx = {-1, 0, 0, 1};
    static int[] dy = {0, -1, 1, 0};
    static int n, m;
    static int[][] graph;
    static int cnt = 0;

    public static void main(String[] args) throws IOException {
        // write your code here
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);
        graph = new int[n + 1][n + 1];
        for (int i = 0; i < n; i++) {
            String[] line = br.readLine().split(" ");
            for (int j = 0; j < line.length; j++) {
                graph[i + 1][j + 1] = Integer.parseInt(line[j]);
            }
        }
        String[] mLines = new String[m];
        for (int i = 0; i < m; i++) {
            mLines[i] = br.readLine();
        }
        long[][] dp = new long[n + 1][n + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + graph[i][j];
            }
        }

        /*for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++)
                System.out.print(dp[i][j] + " ");
            System.out.println();
        }*/

        for (int i = 0; i < m; i++) {
            String[] tmp = mLines[i].split(" ");
            int x1 = Integer.parseInt(tmp[0]);
            int y1 = Integer.parseInt(tmp[1]);
            int x2 = Integer.parseInt(tmp[2]);
            int y2 = Integer.parseInt(tmp[3]);

            long result = dp[x2][y2];
            long outline = dp[x1 - 1][y2] + dp[x2][y1 - 1] - dp[x1 - 1][y1 - 1];
            System.out.println(result - outline);
        }

        bw.close();
        br.close();
    }
}