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

 

11660번: 구간 합 구하기 5

 

 

 

 

문제

N x N 크기의 표가 있을 때, M번 주어지는 (x1, y1) 부터 (x2, y2)까지 합을 구하시오.

 

 

 

 

 

조건

1 <= N <= 1,024

1 <= M <= 100,000

x1 <= x2, y1 <= y2

시간제한 1초

 

 

 

 

 

풀이 방향

완전 탐색(브루트 포스)으로 풀이할 경우 최악의 경우 N x N 크기의 표의 합을 구하는 시간 복잡도는 O(N^2)이고 이 과정을 최대 100,000번 반복해야 하므로 1초라는 시간제한에 걸린다. 대신에, 이전에 다룬 누적합 개념을 2차원 구간에 적용하면 된다. 

 

누적합에 대한 기본 원리는 백준 11659번 풀이를 참고하자.

[백준] 11659번 - 구간 합 구하기 4

 

누적합을 다시 한 번 상기하자면 수열이 주어질 때에 부분 수열 합의 최대 혹은 최소를 구하기 위해 완전 탐색을 이용한다면 최악의 경우 시간 복잡도가 O(N^2)인 연산을 선형으로 바꿀 수 있는 알고리즘이다. 이 문제에서는 누적합을 수열이 아닌 2차원 구간의 표에 적용하면 해결할 수 있다.

 

단순하게 첫 번째 요소부터의 누적값을 배열에 저장했던 것과는 달리 2차원 배열에서는 값 저장 방식이 조금은 복잡하다. 예제 입력 1을 보면서 값을 저장하고 (x1, y1) 부터 (x2, y2) 까지의 합을 구하는 원리를 살펴보겠다.

 

우선 이차원에서 누적합의 기준이 어디부터 어디까지인지 정의해야 한다. 위치 (3, 3) 까지의 누적합이 N(3, 3) 이라면 아래 노란색을 칠한 부분(3 <= x, 3 <= y)의 합을 나타낸다고 하자. 

N(x, y) 다음과 같이 구할 수 있다.

 

N(x, y) = N(x-1, y) + N(x, y-1) - N(x-1, y-1) + (x, y)의 값

 

 

 

 

 

 

아래 빨간 부분은 (x-1, y) 까지의 누적합 N(x-1, y)을 나타내고 파란 부분은 (x, y-1)까지의 누적합 N(x, y-1)을 나타낸다.

 

 

 

 

 

 

 

 

 

만약 N(x-1, y) + N(x, y-1)을 해준다면 아래 연두색 영역이 중첩되어 더해지기 때문에 해당 누적합인 N(x-1, y-1)을 빼주어야 한다. 그러고 나서 현재 위치인 (x, y) 값을 더해준다.

 

 

 

 

 

 

N x N 크기의 누적합 2차원 배열이 완성되었다면, 이제 매번 (x1, y1) 부터 (x2, y2)까지의 누적합을 일일이 계산할 필요 없이 아래의 연산 한 번으로 결과를 얻을 수 있다.

 

result = N(x2, y2) - N(x1-1, y2) - N(x2, y1-1) + N(x1-1, y1-1)

 

이전에는 중첩되는 구간이 두 번 더해졌기 때문에 한 번 - 해주었지만, 구간 누적합을 구할 때에는 두 번 - 되기 때문에 +해준다. 이 또한 그림과 함께 살펴보자. 만약 위 데이터에서 (2, 2) 부터 (4, 3) 까지의 합을 구하면 아래와 같이 된다. 

 

 

 

 

 

 

 

N(4, 3)에서 N(1, 3) 과 N(4, 1) 을 빼면 N(1, 1) 이 중첩되어 두 번 - 된다. 따라서 N(1, 1) 을 한 번 + 해주면 (2, 2) 부터 (4, 3) 까지의 합을 구할 수 있다.

 

 

 

 

 

전체 코드

import java.io.*;

public class Main {
    public static void main (String[] args) throws IOException {
        
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        
        String[] input = br.readLine().split(" ");
        
        int N = Integer.parseInt(input[0]);
        int M = Integer.parseInt(input[1]);
        
        
        int[][] table = new int[N+1][N+1];
        
        
        for (int i = 1; i < N+1; i++) {
            
            input = br.readLine().split(" ");
            
            for (int j = 1; j < N+1; j++) {
                
                table[i][j] = table[i-1][j] + table[i][j-1] - table[i-1][j-1];
                table[i][j] += Integer.parseInt(input[j-1]);
            }
        }
        
        
        StringBuilder sb = new StringBuilder();
        
        for (int i = 0; i < M; i++) {
            
            input = br.readLine().split(" ");
            
            int x1 = Integer.parseInt(input[0]) - 1;
            int y1 = Integer.parseInt(input[1]) - 1;
            int x2 = Integer.parseInt(input[2]);
            int y2 = Integer.parseInt(input[3]);
            
            int sum = table[x2][y2] - table[x1][y2] - table[x2][y1] + table[x1][y1]; 

            sb.append(sum + "\n");
        }
        
        
        System.out.println(sb);
        
        br.close();
    }
}