낚시 (백준 30461)

안녕하세요. 오늘은 낚시를 할 거예요.

문제

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

아이디어

특정 칸 (i,j)에 낚시대를 휘두를 경우 낚을 수 있는 물고기의 개수를 ans[i][j]라고 합시다. 그러면 ans[i][j]는 (1,j)부터 (i,j)까지의 합 + ans[i-1][j-1]이 됩니다. 이를 다 저장한 뒤 출력해주면 됩니다.

소스코드

#include <iostream>
using namespace std;

int arr[3030][3030] = { 0 }, ans[3030][3030] = { 0 };
int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int N, M, Q, i, j;

    cin >> N >> M >> Q;
    for (i = 1; i <= N; i++)
        for (j = 1; j <= M; j++)
            cin >> arr[i][j];

    for (j = 1; j <= M; j++)
    {
        int sum = 0;
        for (i = 1; i <= N; i++)
        {
            sum += arr[i][j];
            ans[i][j] = ans[i - 1][j - 1] + sum; //그 칸에서 낚을 수 있는 물고기의 양
        }
    }

    for (i = 0; i < Q; i++)
    {
        int x, y;
        cin >> x >> y;
        cout << ans[x][y] << "\n";
    }
}

감사합니다.