[BOJ] 11660: 구간 합 구하기 5 (JAVA)

문제

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

 

여담

저번에 풀었던 문제임에도 불구하고 까먹어서 결국 풀이를 참고했다. 그때도 완전히 익히지 않고 넘어갔다는 뜻이겠지..? 이런식으로 설렁설렁 넘어간게 대체 몇 개인지🤦🏻‍♀️ 이번에는 좀 익히자..

 

풀이

2차원 테이블을 사용해서 누적합을 구하면 되는 문제이다. 

 

우선 배열의 값들을 입력받은 후, 아래의 점화식을 이용해 dp 테이블을 채워야 한다.

• dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + arr[i][j]

 

누적합을 이용해 dp 테이블을 채운 후, 이제 원하는 영역의 누적합을 구해야 한다. 이를 위해 다음 그림과 같이 각 구간의 누적합을 더하고 빼주면 된다.

 

코드

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

public class Main {
    static int N, M;
    static int[][] arr, dp;
    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());
        arr = 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());
            }
        }

        // dp 테이블 채우기
        dp = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + arr[i][j];
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int sx = Integer.parseInt(st.nextToken());
            int sy = Integer.parseInt(st.nextToken());
            int ex = Integer.parseInt(st.nextToken());
            int ey = Integer.parseInt(st.nextToken());
            sb.append(dp[ex][ey] - dp[sx - 1][ey] - dp[ex][sy - 1] + dp[sx - 1][sy - 1]).append("\n");
        }
        System.out.println(sb);
    }
}

---

참고

https://cceeun.tistory.com/m/313