[백준/C++] 11660번: 구간 합 구하기 5

문제 & 링크

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

 

풀이

1. 테이블에 값을 입력 할 때 시작점인 (1, 1)부터 현재 위치인 (i, j)까지의 전체 누적합을 dp 테이블에 저장한다.

 

설명: 현재 위치까지의 누적합을 저장하기 위해서는 빨간 사각형(dp[i - 1][j])과 파란 사각형(dp[i][j - 1])을 더하고 둘이 겹치는 부분(dp[i - 1][j - 1])을 빼준 뒤 현재 위치의 값을 더해주면 된다.

 

2. 원하는 범위의 누적합을 구할 때 1에서 만든 dp 테이블을 이용하여 구한다.

설명: 원하는 범위의 누적합인 초록 사각형을 구하기 위해서는 전체 사각형(dp[x2][y2])에서 빨간 사각형(dp[x1 - 1][y2])과 파란 사각형(dp[x2][y1 - 1])을 빼준 뒤 둘이 겹치는 부분(dp[x1 - 1][y1 - 1])을 더해주면 된다.

 

 

코드

#include <iostream>

using namespace std;

int map[1025][1025];
int dp[1025][1025] = {0};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N, M;
    cin >> N >> M;
    
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> map[i][j];
            dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + map[i][j];
        }
    }
    
    int x1, y1, x2, y2;
    
    while (M--) {
        cin >> x1 >> y1 >> x2 >> y2;
        
        int ans = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
            
        cout << ans << "\n";
    }
}