<Algorithm> 204. 2차원 배열의 합(BJO)

 

1. 2차원 배열의 합(BJO)

   사용 알고리즘 :  구간합

• 단순하게 N^3으로 풀수 있는 문제지만 알고리즘도 DP로 되어있기 때문에 DP로 풀어보았다.
• 1차원 배열에 대한 구간합은 쉽게 이해했었는데 2차원배열이 되니까 조금 헷갈리는 부분이 있었다.
• 이렇게 구간합을 사용하면 N^2 만으로 문제를 풀수가 있다.  

 

문제에 대한 접근&생각

 

1. 두 꼭지점에 대한 총합을 구해야함 -> 구간합!
2. 예를 들어 위의 파랑색영역의 합 -> 핑크색영역에서 갈색영역을 뺀다 -> 빨간색영역이 남는다 -> 여기에 노란색 영역을 뺀다
3. 결과적으로 파란영역 - 회색영역이 남기 떄문에 두번빼준 회색영역을 한번 더하면 파란영역의 크기를 구할수있음
4. 갈색영역 -> 오른쪽 V의 x좌표, 왼쪽V의 y좌표-1 , 노란색영역 -> 왼쪽V의 x-1좌표, 오른쪽 V의 y좌표, 회색영역, 왼쪽V -1씩한 좌표

코드 

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

import java.util.Scanner;   public class Main {     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int n = sc.nextInt(), m = sc.nextInt();         int[][] arr = new int[n+1][m+1];         /******************************          * 2차원 배열의 부분합을 구하여           * 원하는 직사각형에 대한 넓이를 구한다.           *******************************/         for(int i = 1; i < n+1; i++)             for(int j = 1; j < m+1; j++)                 arr[i][j] = sc.nextInt();                  for(int i = 1; i < n+1; i++)             for(int j = 2; j < m+1; j++)                 arr[i][j] += arr[i][j-1];                  for(int i = 1; i < m+1; i++)             for(int j = 2; j < n+1; j++)                 arr[j][i] += arr[j-1][i];                  int q = sc.nextInt();                  while(q-->0) {             int i = sc.nextInt(), j = sc.nextInt(),x = sc.nextInt(),y = sc.nextInt();             System.out.println(arr[x][y]- arr[x][j-1]-arr[i-1][y]+arr[i-1][j-1]);         }     } }   Colored by Color Scripter

cs

 

 

 

참고 & 출처  

 

http://meansoup.blogspot.com/2017/09/blog-post.html