[백준] 11660번:구간 합 구하기5(Java 자바)

문제

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

11660번: 구간 합 구하기 5

 

 

풀이 및 소스코드

 

이 문제는 N이 1024이고, 부분합을 100,000번 구해야 함

그때그때 부분합을 구하게 되면 n^2(1024*1024)*m(100,000) => 시간초과

따라서 dp로 풀어야 한다. 

https://subbak2.tistory.com/65

[BOJ 백준] 구간 합 구하기 5(11660) Java

이 분께서 설명을 아주 잘해주셨다 !!!

이해가 안되면 이거 보면 될 듯!!

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


public class Main {
   public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st;
      StringBuilder sb = new StringBuilder();
      st = new StringTokenizer(br.readLine());
      int n = Integer.parseInt(st.nextToken());
      int m = Integer.parseInt(st.nextToken());
      int[][] map = 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++) {
    		  map[i][j] = Integer.parseInt(st.nextToken());
    	  }
      }
      
      // 구간 합 dp에 저장
      int[][] dp = new int[n+1][n+1];
      for(int i=1;i<=n;i++) {
    	  for(int j=1;j<=n;j++) {
    		  dp[i][j] = dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+map[i][j];
    	  }
      }
      
      int x1, y1, x2, y2;
      for(int mm=0;mm<m;mm++) {
    	  st = new StringTokenizer(br.readLine());
    	  x1= Integer.parseInt(st.nextToken());
    	  y1= Integer.parseInt(st.nextToken());
    	  x2= Integer.parseInt(st.nextToken());
    	  y2= Integer.parseInt(st.nextToken());
    	  sb.append(dp[x2][y2]-dp[x2][y1-1]-dp[x1-1][y2]+dp[x1-1][y1-1]).append("\n");
      }
      System.out.println(sb);
   }

}