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

문제 링크 : https://www.acmicpc.net/problem/11660

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> dp;
vector<vector<int>> arr;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //freopen("test.txt", "rt", stdin);
    int n,m;
    cin >> n >> m;
    dp.resize(n + 1,vector<int>(n + 1));
    arr.resize(n + 1,vector<int>(n + 1));
    for(int i = 1; i < n + 1; i++)
    {
        for(int j = 1; j < n + 1; j++)
        {
            cin >> arr[i][j];
            if(j == 1)
            {
                dp[i][j] = arr[i][j];
            }
        }
    }
    for(int i = 1; i < n + 1; i++)
    {
        for(int j = 2; j < n + 1; j++)
        {
            dp[i][j] = arr[i][j] + dp[i][j - 1];
        }
    }
    while(m--)
    {
        int startx,starty,endx,endy,ans = 0;
        cin >> startx >> starty >> endx >> endy;
        for(int i = startx; i <= endx; i++)
        {
            ans += dp[i][endy] - dp[i][starty - 1];
        }
        cout << ans << "\n";
    }
    return 0;
}

구간 합이므로 dp로 풀 수 있겠다고 생각했고, 내가 생각한 방식은 2차원 표의 각 행을 1차원 구간합으로 생각해서 각 행마다 구간합 표를 작성해둔 뒤, 문제에서 제시하는 행구간을 for문을 통해 탐색하며 각 행의 해당하는 구간합들을 더해서 출력하면 된다고 생각했다.

시행착오가 좀 있을 것 같다고 생각했는데 바로 AC를 받았다