[백준] 구간 합 - 11660_구간 합 구하기 Java[자바]

 

바로 전 문제와 마찬가지로 구간합을 이용하면 풀 수 있는 문제이다.

 

다만, 구간 합을 구하는 방법이 전과는 달라졌다.

 

먼저 A[2,2] 까지의 합을 구하는 방법을 생각해보면 S[1,2] + S[2,1] - S[1,1] + A[2,2]로 나타낼 수 있다.

 

이것으로 보아 합 배열을 나타내는 표현식은 S[i,j] = S[i - 1, j] + S[i, j - 1] - S[i - 1, j - 1] + A[i, j] 이다.

 

위에 나온 예제를 활용하여 [2,2]부터 [3,4]까지의 합을 구해보면

 

S[3,4] - S[3,1] - S[1, 4] + S[1, 1]으로 표현이 가능하다.

 

이제 공식으로 변환을 하면

 

[x1, y1] 부터 [x2, y2] 까지의 합은

 

S[x2, y2] - S[x2, y1-1] - S[x1-1, y2] + S[x1-1, y1-1] 으로 표현 가능하다.

 

정답 코드를 보자.

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[][] sumArr = 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++) {
                sumArr[i][j] = sumArr[i - 1][j] + sumArr[i][j - 1] - sumArr[i - 1][j - 1] + 
                    Integer.parseInt(st.nextToken());
            }
        }
        for(int i = 0; i < M; i++) {
            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());
            sb.append(sumArr[x2][y2] - sumArr[x1 - 1][y2] - sumArr[x2][y1 -1] + sumArr[x1 -1][y1 -1] + "\n");
        }
        System.out.println(sb);
    }
}