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

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

 

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

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

---

1.  아이디어

 

누적합 배열을 활용하면 간단하게 해결할 수 있다.

---

2. 문제풀이

 

주어진 영역에 대해 특정 영역의 합을 반복해서 구하는 문제로 2차원 누적합 배열을 생성한 후 prefixSum[x2][y2] - prefixSum[x2][y1] - prefixSum[x1][y2] + prefixSum[x1][y1] 점화식으로 간단하게 특정 영역의 합을 구할 수 있는 점을 활용해 구현했다.

---

3. 코드

 

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        int[][] map = new int[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int[][] prefixSum = new int[1 + N][1 + N];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1] + map[i - 1][j - 1];
            }
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken()) - 1;
            int y1 = Integer.parseInt(st.nextToken()) - 1;
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());

            sb.append(prefixSum[x2][y2] - prefixSum[x2][y1] - prefixSum[x1][y2] + prefixSum[x1][y1]).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
    }
}

---

4. 후기