백준 11660 구간 합 구하기 5

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

표는 2^10까지 커지고 결과를 10만번까지 구해야 할 수도 있다.

합계를 구하기 위해 제시된 공간을 매번 2중 for문으로 훑어 합을 구하게 되면

최악의 상황에는 1024 * 100000 번 연산을 해야한다. 1억번이 넘는 연산이기에 1초 시간제한을 맞추기 어렵다.

 

효율적으로 계산하기위해 메모이제이션을 도입한다.

처음에는 위와 같은 표가 있으면 더한 값을 계속 누적해나가며 이전 행의 누적값에 이어서 누적하여

위 예시와 같은 상황에서

1 3 6 10

12 15 19 24

....

과 같은 형식으로 구현하려 했다. 하지만 이런식으로 구현한다면 2행2열에서부터 3행3열까지 합한다고 할 때

3행 3열의 누적값에서 시작지점의 한칸 전 누적합을 빼고 시작행부터 끝 행까지 돌며 필요없는 값들을 빼주어야 한다.

ex)2행 4열과 3행 1열의 값.

필요이상의 연산이 들어가고 구현도 복잡해진다고 판단해서 방식을 바꾸었다.

 

총 누적값을 구하는 것이 아니라 각 행의 누적값을 구하도록 바꾼다. 예시입력에서는

1 3 6 10

2 5 9 14

....

과 같은 형식으로 저장된다. 이러면 시작행부터 끝 행까지 돌며

끝열의 누적값 - 시작열-1열의 누적값을 더해주면 된다.

구현의 편의를 위해 배열의 크기를 조금 키워 인덱스를 0이아닌 1부터 시작하게 하여

시작열이 첫 열일때도 시작열-1의 상황에서 따로 예외처리를 하지 않도록 해주었다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.*;

public class Main {
    static int n,count;
    static int[][] arr = new int[1100][1100];
    static int[][] dp = new int[1100][1100];
    static int startrow,startcol,endrow,endcol;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String str = br.readLine();
        StringTokenizer token = new StringTokenizer(str);

        n = Integer.parseInt(token.nextToken());
        count= Integer.parseInt(token.nextToken());
        for(int i=1;i<=n;i++){
            str = br.readLine();
            token = new StringTokenizer(str);
            for(int j=1;j<=n;j++){
                arr[i][j]=Integer.parseInt(token.nextToken());
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                    dp[i][j]=dp[i][j-1]+arr[i][j];
            }
        }

        for(int i=0;i<count;i++)
        {
            int result=0;
            str = br.readLine();
            token = new StringTokenizer(str);
            startrow=Integer.parseInt(token.nextToken());
            startcol=Integer.parseInt(token.nextToken());
            endrow=Integer.parseInt(token.nextToken());
            endcol=Integer.parseInt(token.nextToken());
            for(int j=startrow;j<=endrow;j++){
                result+=dp[j][endcol];
                result-=dp[j][startcol-1];
            }
            bw.write(result+"\n");
        }

        bw.flush();
        bw.close();
    }
}