[백준-누적합] 11660 구간 합 구하기 5

Hi, There!
안녕하세요, 바오밥입니다.

---

목차

• 문제
• 풀이

 

---

문제

문제 내용

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

11660번: 구간 합 구하기 5

---

 

풀이

나의 풀이

- 누적합을 활용해 풀이했다.

- 그림장에 그려가며 풀이해 보면 한 눈에 더 와닿을 것이다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] arr = new int[n+1][n+1]; // 원본 값을 저장할 배열
        int[][] graph = 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++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                // 그래프의 X,Y 별 각 범위를 더하고, 겹치는 부분을 뺀 후, 비어있는 좌표 값을 더해주면 됨.
                graph[i][j] = graph[i-1][j] + graph[i][j-1] - graph[i-1][j-1] + arr[i][j];
            }
        }

        for (int k = 1; k <= m; k++) {
            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());
            // 누적합 그래프를 활용해서 주어진 좌표 기준으로 넓은 부분에서 각 꼭짓점 부분들을 빼고 마지막에 겹친 부분들을 다시 더해줌.
            int ans = graph[x2][y2] - graph[x2][y1-1] - graph[x1-1][y2] + graph[x1-1][y1-1];
            sb.append(ans).append("\n");
        }

        System.out.print(sb);
    }
}