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

[문제]

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

11660번: 구간 합 구하기 5

---

[문제 풀이]

DP를 이용한 누적 합 문제이다.

DP[i][j] = DP[i][j - 1] + DP[i - 1][j] - DP[i - 1][j - 1] + arr[i][j]

라는 공식을 이용하자.

 

해당 공식의 의미는 

1	3
2	4

이라는 이차원 배열이 있을때 새로운 DP배열의 [2][2]는 4 + 3 + 2 - 1인 8이 된다는 의미이다.

해당 공식을 사용해서 어떻게 누적합이 되는지 알아보도록 하자. 

 

 

해당 그림안에 숫자가 있다고 가정을 할때 빨간색 칸의 숫자들을 더할 값은 DP[E][6] - DP[E][4](주황색칸) - DP[C][6](보라색 칸) + DP[C][4](파란색 칸) 이 되어야 한다.

즉, 모든 칸을 더한 값 - (주황색 칸 + 파란색 칸) - (보라색 칸 + 파란색 칸) + 파란색 칸 을 하면 나머지 모든 색의 값들이 상쇄되어서 빨간색 칸의 값만 남게 된다.

 

answer = board[x2][y2] + board[x1 - 1][y1 - 1] - board[x1 - 1][y2] - board[x2][y1 - 1];

그렇기에 해당 코드를 이용해서 우리들은 문제에서 요구하는 값을 알 수가 있다.

---

[코드]

#include <iostream>
#include <vector>
#define endl "\n"

using namespace std;

long long board[1025][1025];

long long total_sum(pair<int, int> start, pair<int, int> end){
    long long answer = 0;
    int x1 = start.first;
    int y1 = start.second;
    int x2 = end.first;
    int y2 = end.second;

    answer = board[x2][y2] + board[x1 - 1][y1 - 1] - board[x1 - 1][y2] - board[x2][y1 - 1];

    return answer;
}

int main(){
    int n,m;
    cin>>n>>m;

    long long total = 0;

    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n;j++){
            cin>>board[i][j];
        }
    }

    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n;j++){
            board[i][j] = board[i][j - 1] + board[i - 1][j] - board[i - 1][j - 1] + board[i][j];
        }
    }

    pair<int, int> start;
    pair<int, int> end;
    vector<long long> answer;

    for(int i = 0;i<m;i++){
        cin>>start.first;
        cin>>start.second;
        cin>>end.first;
        cin>>end.second;

        answer.push_back(total_sum(start,end));
    }

    for(int i = 0;i<answer.size();i++){
        cout<<answer[i]<<endl;
    }

    return 0;
}

 

*M이 10만까지 갈 수 있기에

#define endl "\n

코드나 endl을 "\n"으로 바꿔주지 않으면 시간초과가 날 수가 있다.