백준 11660번 (구간 합 구하기 5)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import java.net.Inet4Address;
import java.util.*;

import static java.util.Collections.*;

public class Main {

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

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

    StringBuilder sb = new StringBuilder();




    int graphSize = Integer.parseInt(st.nextToken());
    int ySIze = Integer.parseInt(st.nextToken());

    int[][] graph = new int[graphSize+1][graphSize+1];
    int[][] prefix = new int[graphSize+1][graphSize+1];


    for (int i = 1 ; i <= graphSize; i++)
    {

        StringTokenizer st2 = new StringTokenizer(br.readLine());
        for (int j = 1; j <=graphSize; j++)
        {
            graph[i][j] = Integer.parseInt(st2.nextToken());

            prefix[i][j] = graph[i][j] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1];
        }


    }

    for (int i = 0 ; i < ySIze; i++)
    {
        StringTokenizer st3 = new StringTokenizer(br.readLine());
        int total = 0;
        int x1 = Integer.parseInt(st3.nextToken());
        int y1 = Integer.parseInt(st3.nextToken());
        int x2 = Integer.parseInt(st3.nextToken());
        int y2 = Integer.parseInt(st3.nextToken());


        total = prefix[x2][y2] - prefix[x1-1][y2]- prefix[x2][y1-1]+prefix[x1-1][y1-1];
       sb.append(total).append("\n");
    }

    System.out.println(sb);









}
}

맨 처음에는 브루트포스 방식으로 일일이 다 구했지만 시간 초과가 되어 구간합을 구하는 prefix방식을 이용하게 풀게 되었다. 구간합을 이용하는 식을 이해하기 어려웠지만 신기한 것 같다. 구간합 prefix를 이용하여 2차원 배열을 구하는게 신선한 경험인 것 같다. 이렇게 브루트포스 방식이 안되면 구간합을 이용해야 한다고 생각하는 발상을 기억해야 할 것 같다.