Computer Science/Algorithm

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

simDev1234 2022. 7. 14. 20:27

|  시작하기 전에

지난번에는 일차원 배열에 있는 데이터에 대한 구간합을 구하는 법을 다루었다면,

이번에는 이차원 배열에 있는 데이터에 대한 구간합을 구하는 법을 다루어보았다.

🔖 일차원 구간합에 대한 포스팅은 아래에

 

[백준 11659] 구간합

🛎 11659 구간합 | 문제 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. | 입력 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N

why-dev.tistory.com

 

🛎 11660 구간 합 구하기 5

|  문제 

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.

예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

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

여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.

표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

|  입력

첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)

|  출력

총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.

|  예제 입력

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

 

🔎 문제분석

이 문제도 지난번 일차원 구간합 구하기 문제처럼, 반복문을 사용하면 시간 초과가 난다.

[1] 자료형을 뭘 써야할까? 만약, 여기서 단순 반복을 사용하면 얼마나 오랜 시간이 걸릴까?

아래는 입력값들의 범위인데,

변수명 입력값 범위
N 표의 크기 (행의 크기) 1 ~ 1,024
데이터 배열의 데이터 1 ~ 1,000
M 합을 구해야하는 횟수 1 ~ 100,000

- 표의 크기는 최대 1024 x 1024 이며, 그렇게 되면 최대 1,048,576개의 데이터 수를 받게 된다.

- 데이터의 크기는 최대 1000인데, 최대 표 크기에서 모든 데이터가 1000이라고 할 때,

  최대 범위인 (1, 1)부터 (N, N)까지 최대 구간합은 1,048,576,000가 된다. 

- int타입 데이터의 표현 범위는 -2,147,483,648 ~ 2,147,483,647(약 -21억 ~ 21억, -2^31 ~ 2^31 - 1)이기 때문에 

  구간합의 자료형은 int로 두어도 괜찮다.

 

이제 단순 반복을 했을 때에 얼마나 시간이 걸릴 것인가를 구해 보려고 한다.

[행 x 열]에 대한 이중 반복 루프에서 각 (x1, y1) ~ (x2, y2)까지의 합을 구한다고 하면 

- 시간 복잡도는 O(n^2)가 나온다. (만약 M만큼 범위를 입력받으면서 동시에 구간합을 처리하게 되면 O(n^3) )

 

만약에 최대 크기 배열에 M이 최댓값이 나온다하고 범위가 (1, 1) ~ (N, N)이면- 100,000 x 1024 x 1024(104,857,600,000)만큼 데이터를 확인하고 합을 구한다.

 

[2] 2차원 배열의 구간합을 구하는 방법을 구해보자..

(1) 먼저, 입력 배열은 D[N + 1][N + 1]로, 구간합 배열은 S[N + 1][N + 1]로 만들려 한다.

- 배열 크기는 입력을 (1, 1)부터 (N, N) 사이값으로 받기 때문에 N+1 x N+1으로 하는게 더 쉬웠다..

- (D는 dataArr의 약자고, S는 sumArr의 약자로 임의로 잡았다.)

 

(2) D --> S 로 구간합을 구하는 방법이다.

 

가. 먼저 행이 1일 때와, 열이 1일 때를 보면

  1 2 3 4 구간합
-------->		   1 2 3 4
1 1 2 3 4 1 1 3 6 10
2 2 3 4 5 2 3      
3 3 4 5 6 3 6      
4 4 5 6 7 4 10      

 

- 행이 1인 경우에는, S배열에서 바로 전 열(j - 1)의 값과 D[ i ][ j ] 를 더해주면 된다.

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

- 열이 1인 경우에도, S배열에서 바로 전 행(i - 1)의 값과 D[ i ][ j ] 를 더해준다. 

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

 

나. 행과 열이 1이 아닌 경우를 보면

  1 2 3 4 구간합
-------->		   1 2 3 4
1 1 2 3 4 1 1 3 6 10
2 2 3 4 5 2 3 8    
3 3 4 5 6 3 6      
4 4 5 6 7 4 10      

 

S[2][2]를 구하는 방식을 풀어보면 아래와 같다.

- S[1][2] = D[1][1] + D[1][2]

- S[2][1] = D[1][1] + D[2][1]

- S[2][2] = D[1][1] + D[1][2] + D[2][1] + D[2][2]

              = S[1][2] + S[2][1] - D[1][1] + D[2][2]

 

이를 토대로 공식을 만드면 아래와 같이 만들 수 있다.

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

 

=> 이 상태에서 다시 위의 가.로 넘어가면 N + 1 x N + 1 크기를 만들어줄 것이므로,

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

    만약 행이 1이라면, 그 위인 S[0][N] 값은 모두 0이 될 것이므로

    S [ i ][ j ] = S [ i ][ j - 1 ] + 0 - 0 + D[ i ][ j ]

                  = S [ i ][ j - 1 ] + D[ i ][ j ]  // 나. 의 공식을 그대로 사용해도 무방하다는 걸 볼 수 있다.

    마찬가지로 열이 1일때도 동일하다. 

 

[3] 구간합 배열에서 범위값을 구하는 방법

만약에 (1, 1)에서 (3, 3)까지의 구간합을 구하라 하면 범위값을 구하는 건 쉽다.

- 그냥 S[3][3]를 반환하면 된다.

 

그런데 (2, 2)에서 (3, 3)까지의 구간합을 구하라 한다면?

 

  1 2 3 4 구간합
-------->		   1 2 3 4
1 1 2 3 4 1 1 3 6 10
2 2 3 4 5 2 3 8 15 24
3 3 4 5 6 3 6 15 27 42
4 4 5 6 7 4 10 24 42 64

 

S[3][3]에서 (1, 2) ~ (1, 3)과 (2, 1) ~ (2, 3) 합을 빼주고 (1, 1)값을 더해주어야 한다.

- 만약 범위를 (x1, y1) ~ (x2, y2)라고 한다면

  구간합 범위를 구하는 식 : S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] + S[x1 - 1][y1 -1]

 

⌨️ 코드

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

public class Main {

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        // 입력
        int N = Integer.parseInt(st.nextToken()); // 행의 길이
        int M = Integer.parseInt(st.nextToken()); // 케이스 수

        // 기존 배열 D 
        int[][] D = 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++) {
                D[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 구간합 배열 S  
        int[][] S = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                S[i][j] = S[i][j-1] + S[i-1][j] - S[i-1][j-1] + D[i][j];
            }
        }

        // 케이스당 하나씩 처리
        // 범위 (x1, y1) ~ (x2, y2)의 구간합 구하기
        for (int i = 1; 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 sum = S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] + S[x1 - 1][y1 -1];

            sb.append(sum);
            sb.append("\n");

        }

        System.out.println(sb.toString());

    }
}