[BOJ알고리즘, C++]#11660_구간 합 구하기 5

[BOJ 알고리즘, C++] #11660_구간 합 구하기 5

 

BOJ 알고리즘 문제 풀이, 11660_구간 합 구하기 5

누적 합 알고리즘을 통해 수열의 구간 합을 구하는 문제

 

 

---

 

문제

 

풀이

 

1. 먼저, 2차원 배열의 누적합을 "열" 순으로 누적 합을 계산하는 것이 아니라, "행" 순으로 계산해야 합니다.

2. 누적 합을 계산하는 방법은 아래와 같이 "[i-1][j] + [i][j-1] - [i-1][j-1]"입니다.

prefixSum[i][j] = prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1]

 

 

"행"을 기준으로 누적 합을 계산하다 보면 "중복"으로 누적된 값이 존재합니다! 

 

위 그림을 살펴보면, prefixSum[4]를 위해 prefixSum[2]와 prefixSum[3]의 값이  필요하지만,

이 둘은 이전 누적 합 계산에서 공통적으로 prefixSum[1]이 누적이 되었죠!

 

따라서, 정확한 누적 합 계산을 위해 중복되는 누적 합 부분을 빼주는 것이 필요합니다!

 

코드

#include <iostream>
using namespace std;

int arr[1025][1025];
int dp[1025][1025];
int N, M;
int ans;

int main()
{
    // 수행 시간 감소를 위한 라인
    ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
    
    cin >> N >> M;
    
    for(int i=1; i<=N; i++)
    {
        for(int j=1; j<=N; j++)
        {
            cin >> arr[i][j];
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + arr[i][j];
        }
    }
    
    for(int i=0; i<M; i++)
    {
        int firstX, firstY, secondX, secondY;
        cin >> firstX >> firstY >> secondX >> secondY;
        
        ans = dp[secondX][secondY] - dp[firstX-1][secondY] 
            - dp[secondX][firstY-1] + dp[firstX-1][firstY-1];
        
        cout << ans << '\n';
    }
}


// 참조 : https://donggoolosori.github.io/2020/10/13/boj-11660/ 

/************************** 시간 초과 실패 코드 **************************/

// #include <iostream>
// #include <vector>
// #include <cmath>
// using namespace std;

// typedef long long ll;

// int N, M;

// vector<ll> prefixSum(1,0);

// long long calcInterval(const int firstA, const int firstB, const int secondA, const int secondB)
// {
//     ll ans;
//     ll left =0, right =0; 
    
//     for(int i=0; i<=(secondA - firstA); i++)
//     {
//         left = (N*firstA) - (N-firstB) + (N*i);
//         right = (N*firstA) - (N-secondB) + (N*i);
        
//         ans += prefixSum[right] - prefixSum[left-1];
//     }
    
//     return ans;
// }

// int main()
// {
//     // 수행 시간 감소
//     ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
    
//     cin >> N >> M;
    
//     for(int i=1; i<=(N*N); i++)
//     {
//         ll tmp;
        
//         cin >> tmp;
//         prefixSum.push_back(prefixSum[i-1] + tmp);
//     }
    
//     for(int i=0; i<M; i++)
//     {
//         // [A1][B1], [A2][B2]
//         int a1, b1, a2, b2;
//         int ret;
        
//         cin >> a1 >> b1 >> a2 >> b2;
        
//         ret = calcInterval(a1, b1, a2, b2);
        
//         cout << ret << '\n';
//     }
// }