백준 11660 구간 합 구하기 5 / C++

문제 : 11660

풀이 point

구간 합 구하기 4처럼 미리 구해놓은 덧셈 값들을 통해 O(1)에 값을 구할 수 있다.

합들을 저장해놓은 배열을 완성하고 그 배열을 통해 답을 구할 수 있다.

풀이 방법

합을 구하는 방법은 그전까지 저장해둔 합들을 더한후 거기서 중복된 값을 뺀다.

답을 구할 때도 똑같이 진행한다.

코드

//백준 11660, 구간 합 구하기 5

#include <iostream>

int grid[1025][1025];
int dp[1025][1025];

int main (){

    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);

    int N, M;
    std::cin >> N >> M;

    for(int i{1}; i<=N; ++i){
        for(int j{1}; j<=N; ++j){
            std::cin >> grid[i][j];
        }
    }

    for(int i{1}; i<=N; ++i){
        for(int j{1}; j<=N; ++j){
            dp[i][j] = grid[i][j] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
        }
    }
    int x1, x2, y1, y2;
    for(int i{0}; i<M; ++i){
        std::cin >> x1 >> y1 >> x2 >> y2;
        std::cout << dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1] << '\n';
    }

    return 0;
}