[백준/JAVA] 11660번: 구간 합 구하기 5

🔺 문제

11660번: 구간 합 구하기 5

 

🔺 코드

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

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

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[][] arr = new int[n+1][n+1];
        int[][] sum = 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());
                sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + arr[i][j];
            }
        }

        // 네 개의 정수 받기
        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());

            int result = sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];
            System.out.println(result);
        }   
    }
}

✅ 해결 아이디어
- 20번째 줄, 33번째 줄. 점화식!
- 표 채우고, 누적합 배열 채우는 걸 동시에
- (x1, y1), (x2, y2)를 입력받고 해당 구간의 합 계산
 └ sum[i][j] ⇨ arr[1][1] ~ arr[i][j]까지의 합을 나타냄.
 └ (x1, y1) ~ (x2,y2)까지의 합 : sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[i-1][j-1]

어렵당...ㅠ

---

(참고)

[백준] 11660번 : 구간 합 구하기 5 – JAVA [자바]

[백준] 11660번:구간 합 구하기5(Java 자바)

[BOJ 백준] 구간 합 구하기 5(11660) Java