BOJ#2167 2차원 배열의 합

BOJ#2167 2차원 배열의 합

* 문제

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

* 풀이

단순하게 for loop 2개로 (i, j) ~ (x, y) 원소들을 더해도 되지만

계산량을 줄이기 위해서 아래와 같이 구현해보았습니다.

1. 입력을 받으면서 dp[row][col]를 계산해 놓는다.

dp[row][col] : (row, 1) 부터 (row, col)까지의 합 

2. K개의 쿼리를 입력 받는다. (i, j), (x, y)

3. 행 단위로 합을 구하고 sum 변수에 합산한다.

for ( row = i ... x) {

  sum += dp[row][y] - dp[row][j - 1];

}

---

* 나의 코드

https://github.com/stack07142/BOJ/blob/6ac3127334971a5129da56800f1dc2afa7a32bc7/BOJ%232167_SumOfArrays/src/Main.java

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

/**
 * BOJ#2167 2차원 배열의 합
 * https://www.acmicpc.net/problem/2167
 */

public class Main {

    static int[][] arr = new int[301][301];
    static int[][] dp = new int[301][301];

    public static void main(String[] args) throws IOException {

        int N, M; // 배열의 크기
        int K; // query

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        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());
                dp[i][j] = arr[i][j] + dp[i][j - 1];
            }
        }

        K = Integer.parseInt(br.readLine());

        for (int k = 0; k < K; k++) {

            int i, j, x, y;

            st = new StringTokenizer(br.readLine());

            i = Integer.parseInt(st.nextToken());
            j = Integer.parseInt(st.nextToken());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());

            int sum = 0;
            for (int row = i; row <= x; row++) {

                sum += dp[row][y] - dp[row][j-1];
            }

            bw.write(sum + "\n");
        } // ~ K loop

        bw.flush();
        bw.close();
        br.close();
    } // ~ main
}