백준 11660 구간 합 구하기 5(c++)

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

11660번: 구간 합 구하기 5

이 문제도 마찬가지로 dp를 활용한 풀이입니다. 왜냐하면 값을 하나씩 누적해서 더하면 시간 복잡도가 O(2^20)이므로 dp 배열에 저장할 때, 이전 값을 참조해서 누적 값 자체를 저장해야 합니다. 

<코드>

#include <iostream>
using namespace std;
unsigned long long dp[1025][1025];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int N, M;
    cin>>N>>M;
    int num;
    // dp 초기화(Tabulation)
    dp[0][0] = 0;
    dp[1][0] = 0;
    dp[0][1] = 0;

    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=N;j++)
        {
            cin>>num;
            dp[i][j] = num + dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1];  
            // dp에 누적값을 저장하는 로직
        }
    }

    while(M--)
    {
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        cout<<dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1]<<'\n';
    }
    
}

우선적으로 dp[0][1], dp[1][0], dp[0][0]을 0으로 초기화해줘야 합니다. 왜냐하면, 1행 1열의 값은 누적할 것이 없으므로 값 자체를 저장해야 하기 때문입니다. 

ex) 2행 2열의 누적값을 더하기 방법

dp[2][2] = num(입력받은 2행 2열의 값) + dp[2][1](2행 1열의 누적 값) + dp[1][2](1행 2열의 누적 값) - dp[1][1](1행 1열의 누적 값)

마지막에, 1행 1열의 누적값을 빼준 이유는 겹치는 부분을 제외시켜 주기 위함입니다. 이런 식으로 누적 값을 저장하여 시간 복잡도를 최소화시켜 문제를 풀 수 있었습니다.