[백준] 11660.cpp : 구간 합 구하기 5

www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

---

• 입력받은 (x1,y1) ~ (x2,y2) 의 위치를 하나씩 더해줄 경우 시간초과가 발생하게 된다.
• 해당 구간은 무조건 직사각형의 모양이 되므로, 특정한 규칙을 찾아볼 수 있다.
• 누적합의 기준이 될 축을 행으로 설정하면, (x1,y1) ~ (x2,y2) 구간의 합 = (x1~x2, y2) - (x1~x2, y1) 이 된다.
• 값을 입력받을 때, 각 위치마다 행의 누적합 값을 구해놓으면 쉽게 풀 수 있다.

---

#include <iostream>

using namespace std;

int data[1025][1025];
int ans[1025][1025];
int n, m;
int x1, y1, x2, y2;

int main(void)
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin >> n >> m;
    for(int r = 1 ; r <= n ; r++)
    {
        for(int c = 1 ; c <= n ; c++)
        {
            cin >> data[r][c];
            ans[r][c] = ans[r][c-1] + data[r][c];       // 각 위치의 누적합은 해당 행만의 누적합이 된다
        }
    }
    for(int i = 0 ; i < m ; i++)
    {
        cin >> x1 >> y1 >> x2 >> y2;
        int answer = 0;
        for(int r = x1 ; r <= x2 ; r++)                 // 입력 받은 범위의 행들의 누적합을 더해준다
        {
            answer += ans[r][y2] - ans[r][y1-1];        // y2 위치의 누적합 - y1 위치의 누적합
        }

        cout << answer << '\n';
    }
}