[백준 11660] 구간합 구하기 2 (표) - JAVA

문제

NxN개의 수가 NxN 크기의 표에 채워져 있다. 표 안의 수 중 (X1, Y1)에서 (X2, Y2)까지의 합을 구한다. X는 행, Y는 열이다. 예를 들어 N=4이고, 표가 아래와 같을 때 (2,2)에서 (3,4)까지의 합은 3+4+5+4+5+6)= 27이다.

1번째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다(1<=N<=1,024, 1<=M<=100,000).
2번째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다.
다음 M개의 줄에는 4개의 정수 X1,Y1,X2,Y2가 주어지며 (X1,Y1)에서 (X2,Y2)의 합을 구해 출력한다.
표에 채워져 있는 수는 1,000보다 작거나 같은 자연수다(X1<=X2, Y1<=Y2).

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

 

문제 분석

1. 수의 개수와 합을 구해야하는 횟수는 최대 100,000 -> 구간마다 합을 계산하면 0.5초 안에 불가

2. 구간합 배열이 2차원으로 확장된 것

 

공식

배열 A[i][j]

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

 

합배열 D[i][j]
D[X][Y] = 원본 배열의 (0,0)부터 (X,Y)까지의 사각형 영역 안에 수의 합

1. D[i][j] 의 값을 채우는 구간 합 공식

D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j]

구간 합에 포함되지 않는 행, 열 제거 후 중복 제거된 A[i][j]구간을 더해준다.

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

 

 

2. (X1,Y1)에서 (X2,Y2)까지의 구간 합 공식

D[X2,Y2] - D[X1-1][Y2] - [DX2[Y1-1] + D[X1-1][Y1-1]

 

범위 전의 합을 빼주고 중복 차감한 부분을 더해준다.

 

Q. 2 2 3 4 구간 합은?

 -> D[3][4] - D[1][4] - D[3][1] + D[1][1] = 27

---

pseudo code 작성하기

N(배열 크기), M(질의 개수) 저장하기

for(N만큼 반복) {
    for(N만큼 반복) {
        합 배열 저장하기 D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j]
    }
}

for(M만큼 반복) {
    질의 범위 받기 (X1,Y1), (X2,Y2)
    구간합 출력하기 D[X2,Y2] - D[X1-1][Y2] - [DX2[Y1-1] + D[X1-1][Y1-1]}

 

code

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[][] A = 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++){
        A[i][j] = Integer.parseInt(st.nextToken());
    }
}

int[][] D = new int[N+1][N+1];
for (int i=1; i<=N; i++){
    for(int j=1; j<=N; j++){
        D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[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 = D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1];
    System.out.println(result);
}

 

---

결과 확인

입력	출력
4 3 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 2 2 3 4 3 4 3 4 1 1 4 4	27 6 64