[JAVA]백준 15724번: 주지수

www.acmicpc.net/problem/15724

15724번: 주지수

 

1. 문제 설명

 

네모 왕국의 영토 1*1 단위 구역이 주어지고 단위 구역마다 살고 있는 사람 수가 주어진다.

 

X1, Y1, X2, Y2좌표가 주어질 때 주어진 직사각형 범위에 살고 있는 사람의 수를 구하여라.

 

2. 풀이

 

dp[x][y]= X1=1, Y1=1, X2=x, Y2=y 직사각형 범위에 살고 있는 사람의 수

= dp[x-1][y]+dp[x][y-1]+x,y 좌표에 살고 있는 사람 수 -dp [x-1][y-1]

 

x1, x2, y1, y2 범위의 살고 있는 사람 수를 구할 때는

 

dp [x2][y2]-dp [x2][y1-1]-dp [x1-1][y2]+dp [x1-1][y1-1]로 구할 수 있다.

 

3. 코드

import java.io.*;
import java.nio.Buffer;
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));

        int N,M,test_num;

        StringTokenizer size = new StringTokenizer(br.readLine());

        N = Integer.parseInt(size.nextToken());
        M = Integer.parseInt(size.nextToken());

        int[][] dp = new int[N + 1][M + 1];

        for (int x = 1; x <= N; x++) {

            StringTokenizer temp = new StringTokenizer(br.readLine());

            for (int y = 1; y <= M; y++) {

                int input = Integer.parseInt(temp.nextToken());

                dp[x][y] = dp[x - 1][y] + dp[x][y - 1] + input - dp[x - 1][y - 1];
            }
        }

        test_num = Integer.parseInt(br.readLine());

        for (int t = 0; t < test_num; t++) {

            StringTokenizer location = new StringTokenizer(br.readLine());

            int x1,x2,y1,y2;

            x1 = Integer.parseInt(location.nextToken());
            y1 = Integer.parseInt(location.nextToken());
            x2 = Integer.parseInt(location.nextToken());
            y2 = Integer.parseInt(location.nextToken());

            bw.write(String.valueOf(dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1]) + "\n");
        }


        bw.flush();
        bw.close();
        br.close();

    }



}