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

문제 링크 : 백준 11660번 - 구간 합 구하기 5 자바

 

구간 합 구하기 4(블로그 글 연결) 문제를 먼저 풀고오세요.

 

(1) 합배열 채우기 : 1행 1열을 먼저 계산한 후, 대각선으로 맞추어 계산 (사진 참고, 대각선을 채우려면 1행 1열을 먼저 계산할 필요가 있기 때문)

(2) 구간합 구하기 : (전체-구하는 구간합의 나머지)방식으로 계산하면 구간합을 계산할 수 있다. 최종 합배열 계산 시 숫자 1이 아니라 x1-1 (예제에선 2-1이어서 1임)등임에 유의하여 구현

구현 시 배열 인덱스에 주의하여 구현한다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] nm = br.readLine().split(" ");
        int N = Integer.parseInt(nm[0]);
        int M = Integer.parseInt(nm[1]);
        int[][] input = new int[N][N];
        for (int i = 0; i < N; i++) {
            input[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }

        long[][] sum = new long[N+1][N+1];
        for (int i = 1; i <= N; i++) {
            sum[i][1] = sum[i-1][1] + input[i-1][0];
            sum[1][i] = sum[1][i-1] + input[0][i-1];
        }
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                sum[i][j] = sum[i-1][j] + sum[i][j-1] + input[i-1][j-1] - sum[i-1][j-1];
            }
        }

        for (int i = 0; i < M; i++) {
            int[] xy = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int x1 = xy[0];
            int y1 = xy[1];
            int x2 = xy[2];
            int y2 = xy[3];
            System.out.println(sum[x2][y2] - (sum[x1-1][y2] + sum[x2][y1-1] - sum[x1-1][y1-1]));
        }
    }
}