[백준 11660] 구간 합 구하기 5

구간 합 구하기 5

• 참고 : https://www.acmicpc.net/problem/11660

접근

해당 문제는 이차원 배열에서 누적합을 구해서 주어진 구간의 합을 구해야 한다고 생각했습니다.

1. map이라는 N * N 의 2차원 배열에 누적합을 계산해서 저장
   • 시간 복잡도 : O(N^2)

     (i열 , j-1행의 누적합) + (i-1열, j행의 누적합) - (i-1열, j-1행의 누적합) + (i열, j행)

     
   • i 열 j 행 의 누적합은 아래 식을 통해서 구할 수 있습니다.

2. 주어진 구간에서의 합 구하기해당 과정을 통해서 점화식을 구하면 아래와 같습니다.
3. 
4. 

- 코드를 구현할 때는 map, sumMap의 크기를 N+1로 해서 진행.

전체 코드

package baekjoon_day01;

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

public class PartSum5_11660 {
    static int[][] map;
    static int M, N;
    static int[][] sumMap;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N+1][N+1];
        sumMap = 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++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                sumMap[i][j] = sumMap[i][j-1] + sumMap[i-1][j] + map[i][j] - sumMap[i-1][j-1];
            }
        }

        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());

            sb.append(getSum(a, b, c, d) + "\n");
        }
        System.out.println(sb.toString());
    }

    private static int getSum(int a, int b, int c, int d) {
        return sumMap[c][d] - sumMap[c][b-1]- sumMap[a-1][d] + sumMap[a-1][b-1];
    }
}