[백준] 11660번 - 구간 합 구하기5(△)

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

11660번: 구간 합 구하기 5

 

<풀이>

1. 구간합을 구하기 위해서 가로 기준으로 더해 나가는 합산 테이블 하나, 세로 기준으로 더해나간 합산 테이블 하나해서 총 2개를 준비한다.

2. 2차원 배열의 구간합 배열을 어떤 식으로 구성하느냐가 이 문제를 푸는 열쇠이다.

* 점화식
D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j]

 

3. DP테이블(구간 합 배열)을 다 채운후에 넓이를 구하는 식인 D(x2, y2) - D(x1-1, y2) - D(x2, y1-1) + D(x1-1, y1-1)을 해준다. 

 

<풀이>

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
    static int N, M;
    static int A[][];
    static int D[][];

    public static void main(String[] args) throws Exception {
        InputStreamReader reader = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(reader);
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        A = new int[N+1][N+1];
        D = new int[N+1][N+1];

        for (int i=1; i<=N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j=1; j<=N; j++) {
                A[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        // 구간합 배열 구성하기
        for (int i=1; i<=N; i++) {
            for (int j=1; j<=N; j++) {
                D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j];
            }
        }
        // 원하는 넓이 구하기
        for (int t=0; t<M; t++) {
            st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken());
            int y1= Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2= Integer.parseInt(st.nextToken());
            int sum = 0;
            sum = D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1];
            sb.append(sum).append('\n');
        }
        System.out.println(sb.toString());
    }
}