백준 11660 구간 합 구하기 5 Java [DP, 누적합]

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

11660번: 구간 합 구하기 5

x1 부터 x2까지 하나씩 다 더해서 구했을 때

(1,1)부터 (1024, 1024)까지 합을 구하는 것을 100000번 반복하면 시간복잡도가... 터진다

 

- 풀이 -

1 2 3 4 5 6 7 8 9 10

위와 같은 행이 있을 때 각 자리에 1부터 해당 자리까지 합을 구한다

1 3 6 10 15 21 28 36 45 55

4부터 10까지 합을 구하고 싶으면

1부터 10까지 합에서 1부터 3까지 합을 빼면 된다

55 - 6 = 49

열도 마찬가지로 더하고 나면 예제 1번의 경우

 1  2  3  4
 2  3  4  5
 3  4  5  6
 4  5  6  7
행 더하기
 1  3  6 10
 2  5  9 14
 3  7 12 18
 4  9 15 22
열 더하기
 1  3  6 10
 3  8 15 24
 6 15 27 42
10 24 42 64

(1,1) (4,4)의 경우 64를 출력하면 되는데

(2,2) (4,4)의 경우 64에서 (1,4)와 (4,1)의 값인 10을 빼고 (1,1)값인 1을 더해주면 된다

(X2, Y2) - (X1-1, Y2) - (X2, Y1-1) + (X1-1, Y1-1)

해당 인덱스가 음수인 경우가 생길 수 있고 행열이 1부터 시작하니까 왼쪽과 가장 윗줄에 0을 추가해준다

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

 

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

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());
        int N = 1 + Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[][] arr = new int[N][N];
        for (int n = 1; n < N; n++) {
            st = new StringTokenizer(br.readLine());
            for (int i = 1; i < N; i++) {
                arr[n][i] = Integer.parseInt(st.nextToken()) + arr[n][i-1];
            }
        }
        for (int i = 1; i < N; i++) {
            for (int j = 1; j < N; j++) {
                arr[j][i] += arr[j-1][i];
            }
        }
        for (int m = 0; m < M; m++) {
            st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken())-1;
            int y1 = Integer.parseInt(st.nextToken())-1;
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());
            System.out.println(arr[x2][y2] - arr[x2][y1] - arr[x1][y2] + arr[x1][y1]);
        }
    }
}

행의 이전 값 더해주는 과정은 값을 넣어줄 때 같이 처리해서 코드 반복되는 부분을 제거할 수 있었다