백준_11660 구간 합 구하기2

구간 합 구하기 5

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

106431

49930

36712

44.777%

문제

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.

예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

1	2	3	4
2	3	4	5
3	4	5	6
4	5	6	7

여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.

표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

입력

첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)

출력

총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.

예제 입력 1 

4 3
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
2 2 3 4
3 4 3 4
1 1 4 4

예제 출력 1 

27
6
64

예제 입력 2 

2 4
1 2
3 4
1 1 1 1
1 2 1 2
2 1 2 1
2 2 2 2

예제 출력 2 

1
2
3
4

출처

• 문제를 만든 사람: baekjoon
• 빠진 조건을 찾은 사람: kyma123
• 어색한 표현을 찾은 사람: f52985

 

---

개 어렵다

이 문제는 2차원 구간 합 배열 문제인데, 왓 일단 문제부터 이해 못하겠다.. 

 

2차원 구간 합 배열을 D[i][j]라고 한다면 공식은

D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j]

즉, 이전 합 + 이전 합 - 공통 + 현재 수

 

질의 계산 식은

2 2 3 4 가 들어왔다면 (2,2) 와 (3,4) 사이에 있는 구간의 합을 구하시오

그러면 (3,4) - (3,1) - (1,4) + (1,1)

 

D[X2][Y2] - D[X2][Y1-1] - D[X1-1]D[Y2] + D[X1-1]D[Y1-1]

 

 

 

배열의 크기에 N+1을 해주는 이유는 

만약 2X2의 크기일 때 N+1을 하지 않으면 인덱스 0부터 시작할 때 D[-1] 이 되어서 IndexOutOfBoundsException 에러를 냄

이를 보완하기 위해서 N+1을 하는 것

 

* 예시

1. N+1로 만든 원본 배열
만약 문제에서 주어진 숫자가 1, 2, 3, 4라고 가정해 보겠습니다. 데이터 크기 N=2이지만, 배열 크기를 N+1 (즉 3x3)로 만들면 인덱스 0번 줄이 생기면서 기본값인 0으로 채워집니다.

0번 줄: [0, 0, 0]

1번 줄: [0, 1, 2]

2번 줄: [0, 3, 4]

보시다시피 위쪽과 왼쪽에 '0으로 채워진 안전 테두리'가 생기는 것을 알 수 있습니다.

2. 맨 처음 칸 D[1][1]을 계산하는 순간!
이제 누적 합 배열의 맨 첫 번째 칸(D[1][1])을 앞서 배운 공식으로 구해보겠습니다.

공식: D[1][1] = D[0][1] + D[1][0] - D[0][0] + 현재숫자(1)

여기서 수식에 등장하는 D[0][1], D[1][0], D[0][0]는 모두 방금 만든 0번 테두리에 위치합니다. 즉, 그 값은 모두 0입니다!

계산: 0 + 0 - 0 + 1 = 1

 

 

* 질문

for(int i=1; i<=N; i++){ //왜 1부터?

 

 

 

 

* 정리

공식 암기

1. 구간 합 

-> 이전 + 이전 - 공통 + 현재 수

 

2. 질의에 대한 답 공식

-> D[X2][Y2] - D[X2][Y1-1] - D[X1-1]D[Y2] + D[X1-1]D[Y1-1]

전체 - 빼기1 - 빼기2 + 중복으로 빼진 것

 

 

 

import java.io.*;
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 = new StringTokenizer(br.readLine());
        
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        
        //합 배열 저장
        int A[][] = new int[N+1][N+1];
        
        for(int i=1; i<=N; i++){ //왜 1부터?
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=N; j++){
                A[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        //구간 합 구하기
        int D[][] = new int[N+1][N+1];
        for(int i=1; i<=N; i++){
            for(int j=1; j<=N; j++){
                D[i][j] = D[i-1][j] + D[i][j-1] - D[i-1][j-1] + A[i][j];
            }            
        }
        
        //질의에 답변
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());
            
            int res = D[x2][y2] - D[x2][y1-1]- D[x1-1][y2] + D[x1-1][y1-1];
            System.out.println(res);
            
        }
        
    }
}