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

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

11660번: 구간 합 구하기 5

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N, M, x1, x2, y1, y2, pSum;
    static int[][] arr;
    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();
        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());
            }
        }
        
        int[][] 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] + arr[i][j]; //각 행 별로 누적합
            }
        }
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            x1 = Integer.parseInt(st.nextToken()); y1 = Integer.parseInt(st.nextToken());
            x2 = Integer.parseInt(st.nextToken()); y2 = Integer.parseInt(st.nextToken());
            pSum = 0;
            for (int i = x1; i <= x2; i++) {
                pSum += (dp[i][y2] - dp[i][y1 - 1]);
            }
            sb.append(pSum).append("\n");
        }
        System.out.print(sb);
    }
}

💡 DP

풀이

• (x1, y1) - (x2, y2)를 양 끝으로 하는 사각형 구간에 속하는 값의 합을 구해야 하는 문제
• 처음엔 단순히 각 좌표마다 누적합을 구한 뒤, 왼쪽 초과되는 부분을 빼는 방식으로 진행함
  • 예제에서는 x <= y 좌표인 경우만 나오기 때문에 반례를 생각하지 못했음
  • 하지만 왼쪽 말고도 오른쪽 부분에서도 초과되는 부분이 있을 수 있음 (x > y 인 좌표가 있는 경우)
  • 위 경우까지 고려하려면 너무 복잡해짐 ➡️ 누적합을 구하는 방식이 잘못됐다!
• 각 행마다 누적합을 구하자
  • (x1 ≤ x2, y1 ≤ y2) 조건은 항상 성립하므로 필요한 행만큼 더하고, 시작점 전까지 행을 다시 빼는 방식으로 진행
  • 즉 x1 ~ x2 까지 dp[x][]를 더한 다음, 거기서 dp[x1][y1 - 1], dp[][y1 -1] ... dp[x2][y1-1]를 더한걸 빼줌