[ 백준 11660 ] 구간 합 구하기 5 (C++)

백준의 구간합 구하기5(11660) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

먼저, 구간에 대한 합을 구한 과정을 알아보고, 이를 토대로 정답을 도출하는 과정까지 알아보자.

#1. 구간에 대한 합 구하기

.

위와 같이 맵이 존재할 때, A, B, C, D에 대한 누적합을 모두 구해보자.

지금부터 수식을 하나 사용할 것인데, F[A][B] = C 라는 수식을 사용할 것이다.

F[A][B] = C 의 의미는 "(1 , 1) ~ (A , B) 까지의 누적합은 C입니다." 를 의미한다.

A는 (1 , 1)에 위치해 있는 값이기 때문에, F[1][1] = MAP[1][1]과 동일한 값을 가지게 된다.

따라서, F[1][1]에는 (1 , 1)의 값이 저장되어진다.

B는 (1 , 2)에 위치해 있는 값이다. 따라서 B까지의 누적합은 (1 , 1) + (1 , 2)가 된다.

따라서, F[1][2]에는 (1 , 1) + (1 , 2)의 값이 저장되어진다.

C는 (2 , 1)에 위치해 있는 값이다. C까지의 누적합은 (1 , 1) + (2 , 1)이 된다.

따라서, F[2][1]에는 (1 , 1) + (2 , 1)의 값이 저장되어진다.

D는 (2 , 2)에 위치해 있는 값이다. D까지의 누적합은 (1 , 1) + (1 , 2) + (2 , 1) + (2 , 2) 가 된다.

그럼 이를 저렇게만 넘어가지 말고, 위에서 이야기한 A, B, C 를 이용해서 한번 표현해보자.

(1 , 1) + (1 , 2) + (2 , 1) + (2 , 2)

여기서 빨강색 친 부분에 대한 값은 어디에 저장되어 있을까 ?? 바로 B값인, F[1][2]에 저장되어 있다.

즉, 위의 식은 F[1][2] + (2 , 1) + (2 , 2) 로 표현이 가능하다.
(1 , 1) + (1 , 2) + (2 , 1) + (2 , 2)

여기서 빨강색 친 부분에 대한 값은 어디에 저장되어 있을까 ?? 바로 C값인, F[2][1]에 저장되어 있다.

즉, 위의 식은 F[2][1] + (1 , 2) + (2 , 2) 로 표현이 가능하다.

그럼, F[1][2]와 F[2][1]을 모두 사용해서 식을 표현해보자. 그럼 다음과 같이 표현이 가능하다.

" F[1][2] + F[2][1] + (2 , 2) - (1 , 1) "

위의 식을 풀어서 적어보면 다음과 같다.

(1 , 1) + (1 , 2) + (1 , 1) + (2 , 1) + (2 , 2) - (1 , 1)

이렇게 되면 결국 우리가 구하고자 하는 (1 , 1) + (1 , 2) + (2 , 1) + (2 , 2) 의 값을 구할 수 있다.

중요한 점은, 가장 마지막에 (1 , 1)이 한번 빠지는 것이다. 왜냐하면, F[1][2]와 F[2][1] 에 (1 , 1)이 중복적으로 포함되어서 2번 계산되어지기 때문이다.

그럼, D를 (2 , 2)가 아닌 (x , y)라고 가정해보고 위의 식을 다시한번 적어보자.

F[x][y] = F[x - 1][y] + F[x][y - 1] + MAP[x][y] - F[x - 1][y - 1] 이 된다.

위의 식에서는 단순히 (1 , 1)을 가장 마지막에 뺴주었는데, 위에 (x , y)로 나타낸 식에서는 F[x - 1][y - 1]을 빼주었다.

그 이유는, 위의 맵이 단순히 2 x 2 크기의 맵이라서 (1 , 1)의 값만 뺀 것 처럼 보일 뿐이지, 값이 더 커진다면, F[x - 1][y - 1]의 값을 빼주는 것이 맞다.

따라서 우리는 다음과 같은 식으로 (1 , 1) ~ (x , y) 까지의 누적합을 구할 수 있다.

F[x][y] = F[x - 1][y] + F[x][y - 1] + MAP[x][y] - F[x - 1][y - 1]

#2. 구간합 구하기

위에서 모든 좌표들에 대한 누적합을 모두 구했다. 이제는 정답을 도출하는 과정을 알아보자.

.

이 상황에서 (x , y) ~ (xx , yy)에 대한 구간 합을 구해보자.

우리는 #1의 과정을 통해서 (1 , 1) ~ (x , y)까지에 대한 누적합을 F[x][y]에 저장해놨고, (1 , 1) ~ (xx , yy) 까지에 대한 누적합을 F[xx][yy] 에 저장해 두었다.

F[x][y] 와 F[xx][yy]가 의미하는 칸을 색깔로 칠해보면 다음과 같다.

.

노랑색 칸은 F[x][y]가 의미하는 칸을, 파랑색 칸은 F[xx][yy]가 의미하는 칸을 나타낸 것이다.

그리고 우리가 구하고자 하는 칸을 색깔로 칠해보면 다음과 같다.

.

그러면 먼저 단순하게 생각해보자. 위에 F[xx][yy]가 의미하는 칸이 파랑색 칸에서, 위의 그림에서 흰색 칸 만큼을 빼버린다면 우리는 우리가 구하고자 하는 초록색깔 칸을 구할 수 있을 것이다.

그럼 흰색칸들에 대한 좌표를 나타내면 다음과 같이 표현할 수 있다.

우리가 빼고자 하는 흰색 칸에서 분홍색으로 칠해진 부분(왼쪽 그림)은 아마도 F[xx][y - 1]에 저장되어 있을 것이다.

그리고 또한 우리가 빼고자 하는 노랑색으로 칠해진 부분(오른쪽 그림)은 아마도 F[x - 1][yy]에 저장되어 있을 것이다.

마지막으로, (x - 1, y - 1) 칸은 중복적으로 계산이 되어지고 있다는 것을 확인할 수 있다.

즉, 우리가 구하고자 하는 초록색칸을 색깔로 나타내보면

파랑색칸 - 분홍색칸 - 노랑색칸 + (x - 1 , y - 1) 이 된다.

그럼 이를 식으로 나타내보면..

초록색 칸 = F[xx][yy] - F[xx][y - 1] - F[x - 1][yy] + F[x - 1][y - 1] 이 된다.

이 경우에도 마찬가지로, 마지막에 단순히 (x - 1, y - 1) 하나의 칸에 대해서만 한번 더해주는 것이 아닌, 맵이 더 컸다면

F[x - 1][y - 1] 범위에 대해서 모두 다 2번씩 빠져버리게 되므로, 그 범위에 대해서 다시 한번 더해주어야 한다.

즉 ! (x , y) ~ (xx , yy) 까지의 구간합을 구해라 ! 라고 한다면

F[xx][yy] - F[xx][y - 1] - F[x - 1][yy] + F[x - 1][y - 1] 로 구할 수 있다.

[ 소스코드 ]

#include <iostream>
#include <vector>
#define endl "\n"
#define MAX 1030
using namespace std;
 
int N, M;
int MAP[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 <= N; j++)
        {
            cin >> MAP[i][j];
        }
    }
    for (int i = 0; i < M; 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 <= N; j++)
        {
            Sum[i][j] = Sum[i - 1][j] + Sum[i][j - 1] - Sum[i - 1][j - 1] + MAP[i][j];
        }
    }
    for (int i = 0; i < M; 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;
}