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

구간 합 구하기 5

---

2차원 배열에서 구간 내 합을 구하는 문제
N*N 배열 크기, 구해야 하는 횟수 M

(1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000)

무작정 구하면 최악의 경우 시간초과가 남 O(NM)

누적합 배열을 만들고, 끝 점의 합에서 시작 점의 합을 빼고 사이의 값을 출력하게 구현.
누적합 배열은 어떻게? -> 시작할 때 입력값을 받으면서 누적 배열에 값을 더하면서 저장하기
그렇다면 O(N+M) 으로 처리가능.

처음에는 이렇게 생각했다. 문제를 제대로 읽지 않았기 때문에 사각형 내 합이 아닌, 배열에서 순서대로 읽는 줄 알고 이렇게 쉬운문제가 있나 싶어서 무작정 구현해서 바로 틀려버렸다..

큰 구성은 같다. 누적합 배열을 구해야 한다.
대신 행과 열을 통해 누적합 배열을 구해야 한다.

1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7

기존 해당 배열에서 시작해보면

1 3 6 10
3
6 
10 

이렇게 기초 틀을 잡고, (2,2) 배열은 기존 값과 (1,2)까지의 누적합과 (2,1)까지의 누적합을 더하고, (1,1) 이 2번 더해졌기 때문에 빼줘야 한다. 그렇기에 8

이를 점화식으로 나타내보면

dp[i][j] = num + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];

1 3 6 10 
3 8 15 24 
6 15 27 42 
10 24 42 64 

모든 누적 배열합을 구해보면 이렇게 나온다.

기존에 DP 문제를 풀어봤을 때, 대부분의 문제들은 해당 dp 배열에 접근해서 바로 답을 구했었는데,
시작, 끝 구간이 주어져 있기 때문에 누적합에서 구간합을 구하기위한 추가 계산이 필요하다.

그렇기에 예시에 나온 (2,2) ~ (3,4) 를 구하려고 하면
dp[3][4] 누적합에서 -dp[1][4] -dp[3][1] +dp[1][1] 로 구할 수 있다.
누적합을 구할때와 비슷한 매커니즘을 가지고 있다.

이를 점화식으로 나타내보면

result = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1];

그렇게 어려운 문제는 아니라 한 번 기억하면 다음엔 문제없이 풀 수 있을 듯하다.
문제를 잘 읽는 습관을 들이자..!

---

코드

public class Main {
    public static int n, m;
    public static int[][] dp;

    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());

        dp = 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++) {
                int num = Integer.parseInt(st.nextToken());
                dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + num;
            }
        }

        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 = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1];
            sb.append(result).append("\n");
        }

        System.out.print(sb);
    }
}