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

●문제 출처

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

●정리(요약)
N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오.

●코드

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

public class Main {
	
	static int [] start= new int[2];
	static int [] end= new int[2];
	static int sum;

	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();
		
		// N*N 크기
		int N = Integer.parseInt(st.nextToken());
		//합을 구해야하는 횟수
		int M = Integer.parseInt(st.nextToken());
		
		int [][] arr = new int[N+1][N+1];
		
		for(int i = 1; i<=N ; i++) {
			st= new StringTokenizer(br.readLine()," ");
			for(int j=1; j<=N; j++) {
				arr[i][j]=arr[i-1][j]+arr[i][j-1]-arr[i-1][j-1]+Integer.parseInt(st.nextToken());
			}
		}
		
		
		for(int i =0 ; i<M;i++) {
			sum = 0 ;
			
			st= new StringTokenizer(br.readLine());
			
			start[0]= Integer.parseInt(st.nextToken());
			start[1]= Integer.parseInt(st.nextToken());
			end[0]  = Integer.parseInt(st.nextToken());
			end[1]  = Integer.parseInt(st.nextToken());
			
			sum = arr[end[0]][end[1]]-arr[start[0]-1][end[1]]-arr[end[0]][start[1]-1]+arr[start[0]-1][start[1]-1];
			sb.append(sum).append("\n");
		}
		
		System.out.println(sb.toString());
	}

}

●느낀 점
2차원 DP를 이용하여 푸는 다이나믹 프로그래밍 문제라 풀어보았다.

처음에는 그냥 풀어보자는 생각에 배열을 저장하고 시작부터 끝까지 더하는 방식으로 하니깐 시간초가가 나왔다...
어떻게 구하는지 생각하다가 다른 블로그를 참고하여 작성하였다..ㅎ