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

백준 - 11660

---

풀이

편의를 위해 합 또한 2차원 배열로 저장을 해주었다.

다음은 문제의 예제로 주어진 표에 대한 누적 합을 저장한 배열 sum이다.

[x, y]가 의미하는 바는 [1, 1] 부터 [x, y]까지의 누적 합이다.

배열 sum

만약, [2, 3](초록색), [4, 4](노랑색) 구간의 합을 구할 때, [2, 3]을 기준으로 불필요한 누적 합인 [1, 4](=10), [4, 2](=24)을 빼주면 된다.

하지만, [1, 4]와 [4, 2]를 빼는 과정에서 공통된 누적 합(분홍색)을 두번 빼므로, [1, 2]를 더해주어야 한다.

 

정리하면 다음과 같다.

// input :: 4 4 2 3 
sum[x2][y2]- sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1]
// ex) [4, 4] - [1, 4] - [4, 2] + [1, 2]

---

소스코드

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

---

출처

11660번: 구간 합 구하기 5