[백준]11660번. 구간 합 구하기5(JAVA)

문제

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

---

풀이

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

public class Main {

    static int n, m;

    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());

        int[][] arr = new int[n][n];
        int[][] sumArr = new int[n+1][n+1];

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

        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            int firstX = Integer.parseInt(st.nextToken()); // 2
            int firstY = Integer.parseInt(st.nextToken()); // 2
            int secondX = Integer.parseInt(st.nextToken()); // 3
            int secondY = Integer.parseInt(st.nextToken()); // 4
            int answer = 0;
            for(int j = firstX; j <= secondX; j++){
                answer += sumArr[j][secondY] - sumArr[j][firstY-1];
            }
            System.out.println(answer);

        }
    }




}

첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000)  라는 주어진 조건에 의해 백만 번의 연산을 최대 100,000번 해야 된다는 것을 알 수 있다. 즉, 일반적으로 배열을 추적하며 전부 더하는 단순한 방식을 사용해서는 안 된다는 것이다. 그렇다면 배열에서 사용할 수 있는 좋은 알고리즘은 뭐가 있을까? 부분합이다.

 

문제를 접근하며 부분합이라는 아이디어를 떠올렸지만 2차원 배열에 대해서는 어떻게 접근하는 것이 좋을까 라는 고민이 들었다.

다만 100,000번의 문제를 풀어야 되는 것에 대하여 1000번 접근하는 것은 문제가 없기에, 평소 풀던 1차원 배열에 대한 부분합을 이용하여 그걸 행으로 쭉 두면 되겠다!라는 결정을 하였다. 따라서 각 행에 대해서만 부분합을 갖는 2차원 배열을 별도로 만들어서 이를 처리하였다.