BOJ - 11660 구간 합 구하기 5

11660번 구간 합 구하기 5

NXN 크기의 표에서 시작점(x1, y1)부터 끝점(x2, y2)까지의 합을 구하는 것이다.

다이나믹 프로그래밍 문제로 각 점마다 누적 합을 저장한 후 주어진 점에 대하여 계산을 하면 된다.

원하는 점까지의 누적 합을 구하기 위해서는 원하는 점의 좌표가 (x,y)일 때
(x,y) + (x-1,y)까지의 누적합 + (x,y-1)까지의 누적합 - (x-1,y-1)까지의 누적 합으로 구할 수 있다.

구간 합 계산은 누적되어 더해진 값이 저장된 테이블의 좌표를 기준으로
(x2,y2) - (x1-1,y2) - (x2,y1-1) + (x1-1,y1-1)이라는 계산식을 통하여 구할 수 있다.

위의 두 방식 모두 이전에 사용된 값을 활용하는 전형적인 dp 문제이다.

코드

#include <iostream>


using namespace std;
int arr[1026][1026];
int tab[1026][1026];

int cal(int a, int b, int c, int d)
{
    int sum = 0;
    sum = tab[c][d] - tab[a-1][d] - tab[c][b-1] + tab[a-1][b-1];
    return sum;
}

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    int n,m;
    cin >> n >> m;

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin >> arr[i][j];
        }
    }


/** 누적된 합을 저장하는 테이블 만들기 **/

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

    for(int i=0;i<m;i++)
    {
        int a,b,c,d;
        cin >> a >> b >> c >> d;
        cout << cal(a,b,c,d) << "\n";
    }

    return 0;
}

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