[백준/BOJ/C언어] 11660번 :: 구간 합 구하기 5

 문제 링크 :: https://www.acmicpc.net/problem/11660

---

 Solution

 

 구간 합을 이용하긴 하는데 이차원 배열임을 유의해야 한다. 문제의 예시에서 볼 수 있듯이 그냥 처음부터 끝까지 수를 다 더하는 게 아니라 사각형 모양을 이루는 구간의 합을 구해야 한다. 이건 구간 합을 구할 때뿐만이 아니라, 부분 합을 구할 때도 마찬가지다. 특정 위치의 부분 합을 구하고 싶다면 처음(1, 1)부터 해당 위치까지 사각형을 만들어 그 구역에 있는 숫자들을 합해야 한다. 합하는 방법은 일차원 배열보다는 조금 복잡하지만 어렵지는 않다.

 첫 행은 평범하게 부분 합 구하듯이 쭉쭉 더해 주면 된다. 다음 행부터는 첫 번째 열에 위치하는 경우와 아닌 경우가 달라진다. 첫 번째 열에 위치하면 만들 수 있는 사각형은 표에서 1이 적혀 있는 칸으로 이루어진 사각형일 것이다. 그러니 바로 전 행의 같은 열의 부분 합에 입력받은 값을 더하면 된다. 첫 번째 열이 아닌 경우 만들 수 있는 사각형은 표에서 2가 적혀 있는 칸으로 이루어진 사각형일 것이다. 이 경우 바로 전 행의 같은 열의 부분 합과 같은 행의 바로 전 열의 부분 합을 더한다. 그런데 이러면 중복이 발생한다. 아래 표에서 밑줄이 쳐 진 부분이다. 빼 주면 된다.

 구간 합을 구하는 과정도 이와 비슷하다. (3,2)부터 (4,4)까지의 구간 합을 구한다고 생각해 보자. 3이 쓰인 칸의 합을 구하면 될 것이다. 부분 합을 구하는 과정에서 (4,4)칸의 부분 합은 이미 계산되었다. 처음부터 (4,4)까지의, 4x4 크기의 사각형을 이루는 칸들에 주어진 숫자들의 합일 것이다. 이제 거기서 3이 쓰이지 않은 칸들을 제외해 주어야 한다. 5가 쓰인 칸들이다. (2,4)까지의 부분 합을 빼 주면 필요 없는 두 행이 제외된다. (4,1)까지의 부분 합을 빼 주면 필요 없는 한 열이 제외된다. 그런데 이 부분 합 중에 중복된 부분이 있다. 바로 4가 쓰인 부분이다. 두 번 빼 줬으니 다시 한 번 더해 줘야 한다.

 

1 2 4 5	2 5	5	5
1 2 4 5	2 5	5	5(2,4)
5	3(3,2)	3	3
5(4,1)	3	3	3(4,4)

 이렇게 구간 합을 구할 수 있다. 이해가 안 되는 경우에는 코드를 보며 그려 보기를 추천한다.

---

 Code

#include <stdio.h>
long long sum[1025][1025];
 
int main(void) {
    int N, M, x1, y1, x2, y2, num;
    long long ans;
    scanf("%d %d", &N, &M);
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            scanf("%d", &num);
            if (i == 1) {
                sum[i][j] = sum[i][j - 1] + num;
            }
            else if (j == 1){
                sum[i][j] = sum[i - 1][j] + num;
            }
            else {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + num;
            }
        }
    }
 
 
    while (M--) {
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        ans = sum[x2][y2] - sum[x2][y1 - 1] - sum[x1-1][y2] + sum[x1 - 1][y1 - 1];
        printf("%lld\n", ans);
    }
 
    return 0;
}

---

 Related

2019/07/27 - [코학/알고리즘] - [알고리즘] Prefix sum(구간 합)에 대해 알아보기