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

www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

다이나믹 프로그래밍 알고리즘을 사용해서 푸는 문제입니다.

 

map의 전체 사이즈는 최대 1024x1024이고,

연산을 최대 100,000번 해야하기 때문에, 브루트포스로 풀게되면 당연히 시간초과가 나올 수 밖에 없습니다.

 

시간초과가 나오지 않으려면, DP를 사용해서 각 인덱스별로 누적합을 저장하면 되겠습니다.

 

dp[i][j]는 i, j까지 누적합을 말합니다.

입력을 받을 때부터, dp[i+1][j+1] = dp[i-1][j], dp[i][j-1]값들을 더해주고 입력 값을 더해줍니다.

dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j] - dp[i][j] + map[i][j];
        

추가적으로 중복으로 더해준 부분인, dp[i][j]을 빼줍니다. 

 

그리고, 입력받은 값을 함께 더해주면 i,j까지의 누적합이 됩니다.

 

 

그렇다면, x1,y1부터, x2,y2까지 누적합은 어떻게 구할까요?

 

바로, dp[x2][y2]까지 구한 값에서

dp[x2][y1 -1], dp[x1 - 1][y2]의 값을 빼주면 됩니다.

여기에서, dp[x1-1][y1-1]값을 중복으로 뻈기 때문에,

dp[x1-1][y1-1]을 한번 더해줍니다.

 

전체 코드는 다음과 같습니다.

#include <iostream>

using namespace std;

int n, m;

int map[1025][1025];
int dp[1025][1025];

void solution(){
    cin >> n >> m;

    for (int i = 0; i  < n; i++)
        for (int j = 0; j < n; j++){
            cin >> map[i][j];
            dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j] - dp[i][j] + map[i][j];
        }

    for (int i = 0; i < m; i++){
        int x1, x2, y1, y2;

        cin >> x1 >> y1 >> x2 >> y2;

        cout << (dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1-1][y1-1]) << '\n';
    }
    


}
int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solution();

    return 0;
}