📙[Algo] BOJ30461. 낚시

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

문제 요약

• N * M 의 공간이 존재하고, 각 칸에는 물고기 여럿이 존재
• 가방 먼 칸은 (N, M)
• 무게가 a인 무게추를 매달아 b만큼 힘으로 던지면 (a,b)칸에 미끼가 존재
• 이때, (a,b)에 존재하는 미끼는 1 ≤ i ≤ a인 모든 정수 i에 대해서 (i,b)에 존재하는 모든 물고리를 사로 잡는다.
• 만약 낚싯줄을 한 바퀴 감아 올리면, (a,b)에 위치한 미끼는 (a-1,b-1)로 이동하고, 이동한위치에서 물고기를 사로잡는다.
• 이때, 무게추의 무게와 낚싯대를 휘두를 힘을 알려줄 때마다, 낚싯대를 휘두른 뒤 회수할 때까지 낚싯줄을 감아올리면 몇 마리의 물고기가 사로잡힐지 구해라

시간 제한

• 2초

입력

• 일감호의 크기를 나타내는 정수 N, M과 낚싯대를 휘두를 횟수 Q
  • 1 ≤ N, M ≤ 2000
  • 1 ≤ Q ≤ 30만
• N개의줄에 각 공간의 물고기수 Aij가 주어진다.
  • (i,j)칸에 Aij마리 물고리가 존재
  • 0 ≤ Aij ≤ 500
• Q개의 줄에 건덕이가 미끼에 매달 무게추의 무게를 나타내는 정수 Wi와 낚싯대를 휘두르는 힘을 나타내는 정수 Pi가 공백으로 구분되어 주어짐
  • 1 ≤ Wi ≤ N
  • 1 ≤ Pi ≤ M

출력

• Q개의 줄에 각 낚시에 대해서 미끼를 회수할 때까지 몇 마리의 물고기가 사로잡히는지 출력

접근법

• 문제에서 결국 (a,b)위치에서 물고기를 사로잡는다면, (1,b) ~ (a,b)까지의 물고기의 총 합을 구하고 그 다음 (a-1,b-1)위치로 이동후 똑같이 물고기를 잡아야한다.
• 지도 크기가 최대 2000 * 2000 까지 가능하고, 쿼리가 30만까지 주어지므로 매번 물고기를 잡은 총 합을 구하게 되면 시간초과가 뜨게 된다.
  ⇒ 따라서 각 열마다 누적합을 구한다(열 기준 행 0 ~ N까지 누적합).
  ⇒ 또한 이미 무게 a와 힘이 b일 때 잡은 물고기수를 구한 것은 dp배열에 메모이제이션해서 중복 계산을 피했다.
  ⇒ 이걸 생략하면 시간초과가 뜬다.

코드

import java.io.*;
import java.util.*;

public class Main {
    static int N, M, Q;
    static int[][] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        Q = Integer.parseInt(st.nextToken());

        arr = new int[N + 1][M + 1];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= M; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 누적합 만들기
        for (int j = 1; j <= M; j++) {
            for (int i = 1; i <= N; i++) {
                arr[i][j] += arr[i - 1][j];
            }
        }

        int a, b, sum;
        int[][] dp = new int[2010][2010];
        for (int[] d : dp) {
            Arrays.fill(d, -1);
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < Q; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            sum = 0;

            if (dp[a][b] != -1) {
                sum = dp[a][b];
            } else {
                for (int j = 0; j < a; j++) {
                    if (b - j <= 0) break;
                    sum += arr[a - j][b - j];
                }
                dp[a][b] = sum;
            }

            sb.append(sum).append("\\n");
        }

        System.out.println(sb);
    }
}