[백준 15724]주지수(Java)

문제

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

풀이

DP를 이용해 푸는 문제이다.
DP를 수행할 2차원 배열을 만들었다.
이 2차원 배열은 DP[i][j]가 있으면, (i, 0)부터 (i, j)까지의 값의 합으로 지정하였다.
그 뒤 범위 값(x1, y1, x2, y2)가 들어왔을때
y1부터 y2까지 DP 값을 다 더해주는데, 더해주면서 x1 이하의 열에 대한 DP 값을 빼주었다.

위 그림과 같이 DP[][0]부터 DP[][x-1]까지 빼주고, 이를 y1번째 줄부터 y2번째 줄까지 반복한다.

코드

import java.io.IOException;
import java.util.Scanner;

public class Main {

    public static void main(String args[]) throws IOException {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int M = scan.nextInt();
        int[][] map = new int[N][M];
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                map[i][j] = scan.nextInt();
            }
        }
        int[][] dp = new int[N][M]; //i줄에서 0부터 j컬럼까지의 합
        for(int i=0;i<N;i++){
            dp[i][0] += map[i][0];
        }
        for(int i=0;i<N;i++){
            for(int j=1;j<M;j++){
                dp[i][j] += (dp[i][j-1]+map[i][j]);
            }
        }
        int K = scan.nextInt();
        for(int i=0;i<K;i++){
            int a = scan.nextInt();
            int b = scan.nextInt();
            int c = scan.nextInt();
            int d = scan.nextInt();
            System.out.println(solution(dp, a, b, c, d));
        }
    }
    public static int solution(int[][] dp, int a, int b, int c, int d){
        int sum = 0;
        if(b>=2){
            for(int i=a-1;i<c;i++){
                sum += (dp[i][d-1]-dp[i][b-2]);
            }
        }
        else{
            for(int i=a-1;i<c;i++){
                sum += dp[i][d-1];
            }
        }

        return sum;
    }

}```