11660 구간 합 구하기 5 JAVA

누적합을 2D에서도 적용시킬 수 있다.

 

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

이번 문제를 말로 설명하기엔 제약이 있을 거 같다. 

따라서 유튜브와 같은 곳에서 이런 문제와 관련된 걸 찾아보는 걸 추천한다.

 

 

일단 이 문제는 규칙만 알아내면 정말 별거 없었다.

이 문제 역시 누적합 배열을 만들 때, 한칸 씩 더 만들어주면 예외가 뜨는걸 쉽게 막을 수 있다.

따라서 x,y 한칸 씩 더 만들어줬고,

이차원 배열에 누적합을 만드는 방법은 자신의 윗 배열 값과 왼쪽 배열의 값을 더한 후, 대각선 배열의 값을 빼고, 마지막으로 자신의 위치의 값을 더하는 방식으로 하면 이차원 누적합 배열을 만들 수 있다. 이런 문제를 풀지 않았다면 이 말이 잘 이해가 안갈 수 있으므로,

노트에 그려보면서 이해해보는걸 추천한다.

 

위 공식이 이차원 누적합 배열을 만드는 방법이고, 실제 구하려는 값을 구하기 위해서는 내가 작성한 코드를 보는걸 추천한다.

단순히 말로 설명해봤자 더 복잡하게 만들거 같으므로, 유튜브 같은 시각자료를 참고하는걸 추천한다.

 

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

public class P11660 {
    static int[][] prefixSum;
    static int[][] matrix;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        matrix = new int[N][N]; prefixSum = new int[N+1][N+1];

        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine()," ");
            for(int j = 0; j < N; j++) {
                matrix[i][j] = Integer.parseInt(st.nextToken());
                prefixSum[i+1][j+1] = prefixSum[i+1][j] + prefixSum[i][j+1]
                                   - prefixSum[i][j] + matrix[i][j];
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int y1 = Integer.parseInt(st.nextToken()), x1 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken()), x2 = Integer.parseInt(st.nextToken());
            sb.append(calculatePrefixSum(y1,x1,y2,x2) + "\n");
        }

        System.out.println(sb);
    }

    static int calculatePrefixSum(int y1, int x1, int y2, int x2) {
        return      prefixSum[y2][x2] - prefixSum[y1-1][x2]
                    - prefixSum[y2][x1-1] + prefixSum[y1-1][x1-1];
    }
}