[백준]15724번_주지수

15724번: 주지수

sx,sy,ex,ey 로 테스트 케이스가 주어진다.

• 직사각형 영역 시작 (x,y)와, 끝(x,y)의 좌표가 주어진다.
• 영역이 주어질 때 마다, 매번 계산하는 것은 시간초과를 부를 수 밖에 없다. 영역의 최대 크기는 2^ 20 인데 , test case는 최대 100000이기 때문
• 동적 계획법과, 누적되는 합을 사용해야 할 것 같은데 , 이전의 값을 어떻게 사용할 것인가 ?
• 그렇다고 모든 경우에 대한 bottom up 을 누적으로 한다면.. sx,sy,ex,ey의 경우 자체가 1024 x 1024 x 1024 x 1024임... ㅋㅋㅋ → 이걸 메모리에 저장하는 것은 불가능함.

모르겠다 → 다른 사람 풀이를 봄

30분 고민했다. 모르겠다

• 오.. 💥그냥 [ 시작점은 모두 (1,1)로 ] 하고, [ 끝점만을 누적 ]해 놓고, 이들의 값들을 이용하여 ,💥 더하고 빼서 원하는 영역의 값을 구할 수 있다.
• 즉💥 cache를 2차원의 형태로만 생성💥해서도 풀 수 있다. ( 시작x,시작y,끝x,끝y) 이런 4차원의 형태로 하지 않아도 되었다.
• 항상, 큰 직사각형에서, 두 개의 직사각형을 빼고, 그 두 직사각형의 겹치는 부분을

• 그리고 고려할 것 → 자료형 : 2^20 x 100 = 1억 → int형으로 가능하다.

• sx,sy,ex,ey → calc(ey,ex) - calc(sy,ex) - calc(ey,sx) +calc(sy,sx)

• cache의 값을 bottom up 방식으로 구했다. 먼저 첫 번째 row의 것을

  // (0,0) ~ (ey,ex) 로의 누적값을 구하기 
      public static void bottomUp(int ey,int ex){
          cache[0][0]=area[0][0];
          for(int c=1;c<area.length;c++){
              cache[0][c] = cache[0][c-1]+area[0][c];
          }
          int curRowSum=0;
          for(int r=1;r<area.length;r++){
              curRowSum=0;
              for(int c=0;c<area[0].length;c++){
                  curRowSum+=area[r][c];
                  cache[r][c] = cache[r-1][c] + curRowSum;
              }
          }
      }

틀렸다

• column과 row가 매우.. 혼란스럽게 주어져있다고 생각이 든다.
• 문제에서는 분명 x1,y1,x2,y2 로 주어졌다고 했다. 나는 이것을 평소에 x는 column , y는 row로 풀다 보니 매우 큰 혼란이 왔던 것 같다.
• 따라서 평소에 [y][x]로 하던 것을 [x][y]로 변경해 주어야 한다.

또한, 한 칸의 값을 받을 때부터 누적할 수 있다.

• 다른 분들의 누적합 구하는 과정을 보면
• area의 각 칸에 사는 사람의 수를 구할 때 부터 누적을 한다.
  • 따라서 area[x][y]의 값을 받으면
  • cache[x-1][y]+cache[x][y-1]-cache[x-1][y-1] + area[x][y]와 같다.
  • 이를 하기 위해서, cache는 [1025][1025] 로 하고 row가 0인 줄은 0으로, column이 0인 줄은 0으로 두는게 맞겠다.

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

public class Main{
    // 2^10 x 2^10 = 1048576
    public static int n,m;
    public static long cache[][]=new long[1050][1050];
    public static void Setting() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        for(int x=1;x<=n;x++){
            st = new StringTokenizer(br.readLine());
            for(int y=1;y<=m;y++){
                int a = Integer.parseInt(st.nextToken());
                cache[x][y]= cache[x-1][y]+cache[x][y-1]-cache[x-1][y-1] + a;
            }
        }

/*
        System.out.println();

        for(int r=0;r<=n;r++){
            for(int c=0;c<=m;c++){
                System.out.print(cache[r][c]+" ");
            }
            System.out.println();
        }
*/
        int k = Integer.parseInt(br.readLine());
        int sx=0,sy=0,ex=0,ey=0; //
        for(int t=0;t<k;t++){
            st = new StringTokenizer(br.readLine());
            sx = Integer.parseInt(st.nextToken())-1;
            sy = Integer.parseInt(st.nextToken())-1;
            ex = Integer.parseInt(st.nextToken());
            ey = Integer.parseInt(st.nextToken());
//"("+sy+","+sx+")~("+ey+","+ex+") :"+
            System.out.println((cache[ex][ey]-cache[sx][ey]-cache[ex][sy]+cache[sx][sy]));
        }
    }

    public static void main(String[] args) throws IOException {
        Setting();

    }
}