코드

#include <iostream>
using namespace std;
int a[1025][1025];
int d[1025][1025];

int main(void)
{

    cin.tie(NULL);
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> a[i][j];
        }
    }

    for (int i = 0; i < n; i++)
    {
        if (i >= 1)
            d[0][i] = d[0][i - 1];
        d[0][i] += a[0][i];
    }
    for (int i = 1; i < n; i++)
    {
        d[i][0] = d[i - 1][0];
        d[i][0] += a[i][0];
    }

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

    /*for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << d[i][j] << " ";
        }
        cout << "\n";
    }*/
    for (int i = 0; i < m; i++)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        // 출력
        x1 -= 1;
        y1 -= 1;
        x2 -= 1;
        y2 -= 1;
        int result = d[x2][y2];
        if (x1 >= 1)
            result -= d[x1 - 1][y2];
        if (y1 >= 1)
            result -= d[x2][y1 - 1];
        if (x1 >= 1 && y1 >= 1)
            result += d[x1 - 1][y1 - 1];
        cout << result << "\n";
    }

    return 0;
}

문제 접근 방식

다이내믹 프로그래밍, 구간 합 이용

해결 방법

1. 다이내믹 프로그래밍을 이용하여 0,0 부터 i,j 위치까지의 구간합을 d[i][j]에 구한다. 이는 d[i][j] = d[i-1][j] +d[i][j-1] - d[i-1][j-1] +a[i][j] 로 구할 수 있다.

2. (x1, y1) , (x2,y2) 가 주어졌으면 우리가 구하고자하는 넓이는 d[x2][y2] -d[x1-1][y2] - d[x2][y1-1] + d[x1-1][y1-1] 이다.

기억해야 할 것

시간 초과가 났다. 이는 for 문에서 입출력 방식이 느릴 경우, 여러줄 입력받거나 출력할 때 시간초과가 날수 있다고 한다. 이를 방지하기 위해 다음 세 문장을 써준다.
https://www.acmicpc.net/problem/15552

cin.tie(NULL);
    ios::sync_with_stdio(false);
    cout.tie(NULL);