11660번 - 구간 합 구하기 5(C++)

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

저번에 했던 구간합 문제의 2차원배열 버전이다.

 

이 문제도 시간이 촉박해서 구간합공식을 이용하는 문제다.

 

저번에 배운 cin,cout 최적화와 endl대신 개행문자를 사용했다.

#include <iostream>
#include <vector>
using namespace std;

//구간 합 문제
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int size, quiz;

    cin >> size >> quiz;

    //2차원 배열의 원본A, 구간합B를 0으로 초기화하여 사이즈보다 하나 크게 생성
    //=> 구간합 공식을 위해 0으로 채워진 공간이 필요함
    vector<vector<int>> A(size+1, vector<int>(size+1,0));
    vector<vector<int>> B(size+1, vector<int>(size+1,0));

    //원본배열 받으면서 구간합배열 생성
    for (int i = 1; i <= size; i++) {
        for (int j = 1; j <= size; j++) {
            cin >> A[i][j];
            
            //구간합을 구하려는 위치 기준 위에거,왼쪽거 더하고 왼쪽대각선에 있는거 빼고
            //원본배열의 현위치값 더하기
            B[i][j] = B[i - 1][j] + B[i][j - 1] - B[i - 1][j - 1] + A[i][j];
        }
    }

    for (int i = 0; i < quiz; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        //x1,y1 ~ x2,y2사이의 구간합 구하는 공식
        int result = B[x2][y2] - B[x1 - 1][y2] - B[x2][y1 - 1] + B[x1 - 1][y1 - 1];
        cout << result << "\n";

    }

    return 0;
}

 

그래서 저 공식이 어떻게 나오는건지 알아보자

 

 

우리는 다음과 같은 2차원 배열을 입력받을 예정이다.(회색배경은 좌표를 표현하는 숫자다)

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

 이 배열로 합배열을 만들면

	1	2	3	4
1	1	3	6	10
2	3
3	6
4	10

 

이런식으로 1행 1열이 채워진다.

원본배열 A와 합배열 B가 있다고 했을때

행 구간합 공식:B[i][j] = B[1][j-1] + A[1][j]

열 구간합 공식:B[i][j] = B[i-1][1] + A[i][1]

 

2,2부터는 위에 코드처럼

구간합을 구하려는 위치 기준 위에거,왼쪽거 더하고 왼쪽대각선에 있는거 빼고 원본배열의 현위치값 더하기
공식:B[i][j] = B[i - 1][j] + B[i][j - 1] - B[i - 1][j - 1] + A[i][j];

이때 i-1같은 공식의 연산을 위해 크기가 하나씩 더 큰 벡터를 생성해뒀다.

그 하나 더 큰 공간에는 0이 있어서 계산에 영향을 주지 않는다.

 

0	0	0	0	0
0	1	3	6	10
0	3
0	6
0	10

 

이런 느낌인것.

저 공식으로 모두 채우면

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

라는 벡터 B가 만들어진다.

 

이제 구간합을 구해볼건데.

 

일단 공식은 B[x2][y2] - B[x1 - 1][y2] - B[x2][y1 - 1] + B[x1 - 1][y1 - 1] 이다.

 

왜 그렇게 나오는지 살펴보자

예를들어 2,2~3,4라고 생각해보자

 

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

저 파란 범위의 구간합을 구하려면

(1,1)부터 (3,4)의 구간합에서 

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

 

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

두개의 노란 범위를 빼고 

 

 

중복으로 뺀 1,1을 다시 더해줘야 한다.

(2,2)와 (3,4)를

 B[x2][y2] - B[x1 - 1][y2] - B[x2][y1 - 1] + B[x1 - 1][y1 - 1] 에 대입해 보면

 B[3][4] - B[2 - 1][4] - B[3][2 - 1] + B[2 - 1][2 - 1] => B[3][4] - B[1][4] - B[3][1] + B[1][1] = 27 이다.