백준 30461 - 낚시 (C++)

문제

• 문제 링크

  
   BOJ 30461 - 낚시 
  

• 문제 요약

$N*M$개의 칸 각각에 존재하는 물고기의 정보가 주어진다.
$Q$개의 쿼리에 대해, 미끼를 회수할 때까지 몇 마리의 물고기가 사로잡히는지 출력하자.


• 제한

TL : $2$ sec, ML : $1024$ MB




$1 ≤ N,M ≤ 2,000$

$1 ≤ Q ≤ 300,000$

$0 ≤ a_{ij} ≤ 500$

알고리즘 분류

• 다이나믹 프로그래밍 (dp)
• 누적 합 (prefix_sum)

풀이

$dp[i][j]$에 $Q(i, j)$의 답을 저장한다고 생각해보자.

계단식으로 답을 계산할 수 있으므로, 먼저 $dp[i][j]$는 $dp[i - 1][j - 1]$을 포함한다.

여기에 추가적으로 $A[i][j] + A[i - 1][j] + A[i - 2][j] + ... + A[1][j]$ 을 포함해야 하는데, 이 역시 $dp$에 기록된 값을 이용해 다음과 같이 정리할 수 있다.

$A[i][j] + dp[i - 1][j] - dp[i - 2][j - 1]$.

이를 모든 $A_{ij}$에 대해 전처리해 두면, 쿼리당 $O(1)$에 응답할 수 있다.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, m, q; cin >> n >> m >> q;
 
    int dp[2001][2001]{};
    for (int i(1); i <= n; i++)
        for (int j(1); j <= m; j++)
        {
            int x; cin >> x;
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] + x;
            dp[i][j] -= dp[max(0, i - 2)][j - 1];
        }
 
    for (int i, j; q--;)
    {
        cin >> i >> j;
        cout << dp[i][j] << '\n';
    }
}

comment

끝