[ 백준 2167 ] 2차원 배열의 합 (C++)

백준의 2차원 배열의 합(2167) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

2차원 배열의 합을 구해야 하는 문제이다.

이 문제는 "보다 특별한 누적합의 개념"을 이용해서 해결할 수 있다.

그럼 지금부터는 "보다 특별한 누적합" 에 대해서 알아보자.

보통 누적합 이라고 하는 것은 1번부터 특정 X번 까지의 누적된 합을 저장하는 것을 의미한다.

이 개념을 2차원 배열에도 그대로 적용을 시킬 건데, 2차원은 말 그대로 1개의 차원만 존재하는 것이 아니라, 또 하나의 차원이 존재한다. 그래서 또 하나의 차원을 고려한 누적합을 적용시켜 볼 것이다.

지금부터 누적합을 편하게 수식으로 나타내기 위해서 다음과 같은 수식을 사용할 것이다.

Sum[][] 이라는 수식을 사용할 것인데, Sum[A][B] = C의 의미는 "(1, 1)부터 (A, B)까지의 누적합의 값은 C입니다." 를 의미한다.

.

위와 같은 하나의 예시를 통해서 알아보자. 편의상 가장 왼쪽위의 좌표를 (1, 1), 가장 오른쪽 아래의 좌표를 (3, 3) 이라고 표현하자.

지금부터 모든 좌표들에 대해서 (1, 1) ~ (x, y) 까지의 누적합을 계산해볼 것인데, 단순히 다 더하는 것이 아니라

1 ~ x 까지에 있는 좌표들 중, 1 ~ y까지에 있는 좌표들의 합으로만 계산을 할 것이다.

한번 직접 계산을 하면서 위의 말을 이해해보자.

먼저, (1, 1)의 누적합은 그대로 (1, 1)값 그대로를 가지게 된다. 왜 ? 그 이전에 존재하는 좌표가 없기 때문이다.

Sum[1][1] = 1

(1, 2)의 누적합을 계산해보자. 그럼 이 말은 즉, (1, 1)부터 (1, 2)까지의 합을 구하는 것이니 결과적으로 1 + 2 = 3이 된다.

Sum[1][2] = 3

(1, 3)까지의 누적합을 계산해보자. 그럼 (1, 1) ~ (1, 3)까지의 좌표들을 모두 더한 값이니 계산을 해보면 1 + 2 + 3 = 6이 된다. Sum[1][3] = 6

그럼 그 다음에 (2, 1)까지의 누적합을 계산해보자. 여기서부터는 위에서 했던 말에 대해서 고려를 해주어야 한다.

왜냐하면, (1, 1) + (1, 2) + (1, 3) + (2, 1) 의 값을 계산하려는 것이 아니기 때문이다.

위에서 이런말을 했었다.

"1 ~ x 까지에 있는 좌표들 중, 1 ~ y까지에 있는 좌표들의 합으로만 계산"

그대로 적용시켜보자.

(2, 1)이라는 좌표를 위의 말에 그대로 대입시켜서 다시 적어보면 다음과 같다.

"1 ~ 2 까지에 있는 좌표들 중, 1 ~ 1까지에 있는 좌표들의 합으로만 계산"

즉 ! (1 , 1) + (2 , 1) 까지의 값을 계산한 것이 우리가 하고자 하는 2차원 배열에서의 누적합 이라는 것이다.

즉, (2, 1)까지의 누적합은 1 + 4 로써 '5'가 된다.

Sum[2][1] = 5

그림으로 표현해보면 다음 부분을 계산한 것이다.

.

[ (2 , 1)까지의 누적합을 계산한 범위 ]

그럼 이어서 (2 , 2)를 계산해보자. 마찬가지로 똑같이 계산을 하기 위해서는 다음의 범위들을 계산해 주면 된다.

.

위의 범위를 계산해주면 되는데, 그럼 그 다음 좌표로 넘어가기 전에 계산하기 위한 일반적인 식을 한번 계산해보자.

(2 , 2)까지의 누적합을 구하기 위해서 위와 같이 4개의 좌표를 더해주면 되는데, 사실 모든 좌표를 다 더해줄 필요는 없다.

왜냐하면 우리는 이전에 나왔던 좌표들에 대한 누적합을 모두 구해놨기 때문이다.

(1 , 2)에 대한 누적합은 '3'이라는 것을 위에서 계산(Sum[1][2])했었는데, 이 값은 (1 , 1) + (1 , 2)의 값이 계산된 수치이다.

즉 ! 우리는 (1 , 2)에 대한 누적합을 이미 알고 있기 때문에 우리가 계산하고자 했던 4개의 좌표중에서 다음과 같이 파랑색으로 표시된 2개의 좌표는 계산할 필요가 없어진다는 것을 알 수 있다.

.

그래서 이제 왼쪽에 있는 좌표인 (2, 1)을 구하려고 보니, (2 , 1)도 계산을 한 적이 있다. 우리는 위에서 Sum[2][1]의 값이 5라는 것을 구해놓았다. 그런데 ! 잘 보니 Sum[2][1] 이라는 것은 (1 , 1) + (2 , 1) 에 대한 결과값이 저장되어 있는 것이다.

즉 ! 우리는 Sum[1][2] 와 Sum[2][1]의 값 만으로도 Sum[2][2]의 값을 계산할 수가 있다는 것을 의미한다.

바로, Sum[2][2]의 값은 (1 , 1) ~ (1 , 2) 까지 계산된 결과값을 가지고 있는 Sum[1][2] 와 (1 , 1) ~ (2 , 1)까지 계산된 결과값을 가지고 있는 Sum[2][1]을 더한 값에다가 (2 , 2)의 좌표값을 더해주면 된다는 것이다.

정리해보면 Sum[2][2] = Sum[1][2] + Sum[2][1] + (2 , 2) 가 되는 것이다.

그런데 ! 한가지 문제점이 있다. 위의식의 우항을 한번 좌표로 풀어서 써보면

Sum[2][2] = (1 , 1) + (1 , 2) + (1 , 1) + (2 , 1) + (2 , 2) 가 된다.

우리가 계산하기 위한 (2 , 2)까지의 누적합을 좌표로 적어보면, (1 , 1) + (1 , 2) + (2 , 1) + (2 , 2) 이다.

그런데 위의 식에서는 (1 , 1)에 중복되어서 2번 계산된 것을 확인할 수가 있다.

따라서 ! 이 중복된 계산을 한번 빼주어야 한다.

Sum[2][2] = Sum[1][2] + Sum[2][1] + (2 , 2) - (1 , 1) 이 되어야 한다는 것이다.

위와같이 계산을 하면 정확하게 계산을 할 수가 있다.

그럼 위의 식에서 (2 , 2) 대신 (x , y) 를 한번 넣어서 식을 정리해보자.

Sum[x][y] = Sum[x - 1][y] + Sum[x][y - 1] + (x , y) - (x - 1 , y - 1) 이 된다는 것이다.

그럼 본인이 (1 , 1) 부터 (3 , 2)까지의 누적합에 대한 결과를 가져올테니, 마지막으로 (3 , 3)까지의 누적합을 위에서 구해놓은 식을 통해서 한번 구해보자.

.

빈칸을 한번 채워보자. 왼쪽은 누적합에 대한 2차원 배열이고, 오른쪽은 처음에 말했던 원본 배열이다.

위에서 구한 수식을 그대로 써보면 Sum[3][3] = Sum[2][3] + Sum[3][2] + (3 , 3) - (2 , 2) 가 된다.

계산을 해보면 Sum[3][3] = 21 + 27 + 9 - 5 = 52 가 된다.

그럼 확인해보기 위해서 (1 , 1) ~ (3 , 3)까지의 모든 원소를 더해보면 1 + 2 + 3 + 4 +...+ 9 를 계산해보면 45가 나오게 된다.

이상하게 결과값이 달라진다. 왜그럴까 ??

다시한번 우리가 위에서 구했던 수식을 잘보자.

Sum[3][3] = Sum[2][3] + Sum[3][2] + (3 , 3) - (2 , 2) 인데 여기서 Sum[2][3]과 Sum[3][2]가 가지고 있는 범위를 한번 표현해보자.

.

위의 그림이 Sum[2][3]이 계산한 범위를 색깔로 칠해놓은 것이다.

.

위의 그림이 Sum[3][2]가 계산한 범위를 색깔로 칠해놓은 것이다.

위의 2개의 그림이 중복적으로 표현하고 있는 범위만 다시 색깔을 칠해보면...

.

위의 그림에서 파랑색으로 칠해진 부분과 같이 4개의 좌표가 중복적으로 계산되어 지고 있다.

그런데, 저 4개의 좌표를 우리는 이미 계산을 한 적이 있었다. 바로 ! Sum[2][2]의 값이다.

즉 ! 우리가 (2 , 2)를 위에서 계산할 때에는 일반화된 식을
Sum[x][y] = Sum[x - 1][y] + Sum[x][y - 1] + (x , y) - (x - 1 , y - 1) 라고 구했는데, 사실은 가장 마지막에

빼줘야 하는 중복된 좌표가 1개가 아니라는 것이다. 즉 ! 위의 식을

Sum[x][y] = Sum[x - 1][y] + Sum[x][y - 1] + (x , y) - Sum[x - 1][y - 1] 로 계산을 해줘야 한다는 것이다.

우리는 이렇게 2차원 배열에 대한 누적합을 계산할 수가 있다.

최종적으로 정리를 해보면...

Sum[x][y] = Sum[x - 1][y] + Sum[x][y - 1] + (x , y) - Sum[x - 1][y - 1]

그런데... 위의 값을 왜 계산한 것일까 ?? 문제에서 무조건 누적합을 구하라는 것도 아닌데, 왜 (1 , 1)부터 (x, y)까지의 합을 계산하는 과정을 한 것일까 ?? 지금부터는 본격적인 문제 풀이에 들어가보자.

.

우리가 위에서 구했던 2차원 배열과, 그 배열에서 구한 누적합을 저장한 2개의 그림을 가져왔다.

문제에서 입력이 정말 보기좋게 (1 , 1) , (2 , 3) 이런식으로 주어지면 정말 쉽게 계산이 가능하겠지만

(1 , 2) , (2 , 3) 이런식으로 주어진다는 것이다.

그럼 (1 , 2)부터 (2 , 3)까지의 합을 한번 구해보자.

일단 눈으로 계산해보면 2 + 3 + 5 + 6 = 16이 된다.

먼저 우리가 구해놓은 Sum[1][2]와 Sum[2][3]을 한번 이용해보자.

가장 왼쪽 그림은 우리가 구하고자 하는 합의 범위 , 가운데 그림은 Sum[1][2]가 포함하고 있는 범위 , 오른쪽 그림은

Sum[2][3]이 포함하고 있는 범위이다.

그럼 Sum[2][3] 에서, (1 , 1)과 (2 , 1)만 잘 빼내면 (1 , 2) ~ (2 , 3)의 합을 구할 수가 있을 것이다.

더군다나, (1 , 1)과 (2 , 1)은 Sum[2][1]에 하나로 계산되어 있기 때문에 Sum[2][1]의 값만 빼내면 계산을 할 수 있을 것이다.

그럼 우리는 위의 경우로 추측해봤을 때, Sum[2][3] - Sum[2][1]을 하면 (1 , 2) ~ (2 , 3)까지의 합을 구할 수 있다고 예상해볼 수 있다.

그럼 (2 , 2) ~ (3 , 3)의 합을 구해보자.

가장 왼쪽은 우리가 구하고자 하는 합의 범위 , 가운데 그림은 Sum[2][2]의 범위 , 오른쪽 그림은 Sum[3][3]의 범위이다.

이번 경우에는 더 많은 부분을 빼줘야 한다.

그림으로 봤을 때 빼줘야 하는 부분을 적어보면, Sum[3][3]에서 Sum[1][3]과 Sum[3][1]을 빼주면 될 것 같ㄴ다. 이렇게 2개의 부분을 빼준다면 우리가 원하는 결과값을 얻을 수 있을 것이다.

즉, (2 , 2) ~ (3, 3)까지의 합 = Sum[3][3] - Sum[1][3] - Sum[3][1] 이 되는 것이다.

그런데 ! 저 좌표들의 값을 어떻게 구하냐는 것이다.

(2 , 2)를 (x , y) , (3 , 3)을 (xx , yy) 로 치환시켜서 생각을 해보자.그러고 위의 숫자들을 x , y들로만 한번 표현을 해보겠다.

(x , y) ~ (xx , yy) 까지의 합 = Sum[xx][yy] - Sum[x - 1][yy] - Sum[xx][y - 1]

이렇게 표현을 할 수가 있다.

위에서 계산한 (1 , 2) ~ (2 , 3)도 마찬가지이다.

(1 , 2) ~ (2 , 3)까지의 합 = Sum[2][3] - Sum[2][1] 이라고 추측했었는데, 위의 식에 대입시켜보면
(1 , 2) ~ (2 , 3)까지의 합 = Sum[2][3] - Sum[0][3] - Sum[2][1] 이 된다.

Sum[0][3] 의 값은 0이다.

즉 ! 위와 같이 한번 표현해 보았는데 여기서도 아까 누적합을 계산했을 때와 같이 중복된 계산이 한번 발생한다.

(2 , 2) ~ (3 , 3)을 계산하기 위해서 Sum[3][3] 에서 Sum[1][3] 과 Sum[3][1]을 빼버리게 되면...

.

위의 그림과 같이 (1 , 1)이 중복적으로 2번이 빠져버리게 된다. 즉 ! (1 , 1)의 값이 계산되지 않는다는 것이다.

그래서 (x , y) ~ (xx , yy)의 합을 구하기 위해서는

Sum[xx][yy] - Sum[x - 1][yy] - Sum[xx][y - 1] + Sum[x - 1][y - 1] 과 같이 마지막에 중복적으로 2번이 빠진 부분을 한번 더해줘야 한다는 것이다 !

이해하면 간단한 내용인데 설명이 길어진 것 같다.

마지막으로 최종적으로 정리를 해보면

(x , y) ~ (xx, yy) 까지의 합 = Sum[xx][yy] - Sum[xx][y - 1] - Sum[x][yy - 1] + Sum[x - 1][y - 1]

[ 소스코드 ]

#include <iostream>
#include <vector>
 
#define endl "\n"
#define MAX 310
using namespace std;
 
int N, M, K;
int Arr[MAX][MAX];
int Sum[MAX][MAX];
vector<pair<pair<int, int>, pair<int, int>>> Cmd;
 
void Input()
{
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            cin >> Arr[i][j];
        }
    }
    cin >> K;
    for (int i = 0; i < K; i++)
    {
        int a, b, c, d; cin >> a >> b >> c >> d;
        Cmd.push_back(make_pair(make_pair(a, b), make_pair(c, d)));
    }
}
 
void Solution()
{
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            Sum[i][j] = Sum[i - 1][j] + Sum[i][j - 1] - Sum[i - 1][j - 1] + Arr[i][j];
        }
    }
 
    for (int i = 0; i < K; i++)
    {
        int x = Cmd[i].first.first;
        int y = Cmd[i].first.second;
        int xx = Cmd[i].second.first;
        int yy = Cmd[i].second.second;
 
        cout << Sum[xx][yy] - Sum[xx][y - 1] - Sum[x - 1][yy] + Sum[x - 1][y - 1] << endl;
    }
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}