[백준]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();
}
}
Author And Source
이 문제에 관하여([백준]15724번_주지수), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ynoolee/백준15724번주지수저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)