[BOJ] 11660. 구간 합 구하기5

간단해 보이는 문제지만 동적프로그래밍을 사용해야하는 문제이다.

N=1000 이고 M=100000이므로 최악의 경우에는 for문을 사용하였을때 1억을 넘어가므로 일반적인 방식으로는 풀이를 할 수 없다. 그래서 arr에 저장할때 행별로 더해주며 누적값을 저장하였다. 그 후 행별로 누적된 값을 이용하여 연산을 하는 방식으로 문제를 해결해주었다.

package boj2;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_bj_11660_구간합구하기5 {
    public static void main(String[] args) throws Exception {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        st=new StringTokenizer(br.readLine());
        int N=Integer.parseInt(st.nextToken());
        int M=Integer.parseInt(st.nextToken());
        
        int[][] arr=new int[N][N];
        for(int i=0;i<N;i++) {
            st=new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++) {
                int num=Integer.parseInt(st.nextToken());
                if(j==0) {
                    arr[i][j]=num;
                }else {
                    arr[i][j]=num+arr[i][j-1];
                }
            }
        }
        
        for(int i=0;i<M;i++) {
            int sum=0;
            st=new StringTokenizer(br.readLine());
            int a=Integer.parseInt(st.nextToken())-1;
            int b=Integer.parseInt(st.nextToken())-1;
            int c=Integer.parseInt(st.nextToken())-1;
            int d=Integer.parseInt(st.nextToken())-1;
            
            for(int ii=a;ii<=c;ii++) {
                if(b==0) {
                    sum+=arr[ii][d];
                }else {
                    sum+=(arr[ii][d]-arr[ii][b-1]);
                }
            }
            
            System.out.println(sum);
        }
        
    }
}