[백준/알고리즘] 11660 - 구간 합 구하기5 (자바/Java)

문제

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)까지 합을 구해 출력한다.

 

 

Step1. 문제 분석

1. N(배열 크기), M(합을 구해야하는 횟수)를 입력받는다.
2. NxN 개의 수를 입력받아 크기가 N인 2차원 배열에 저장하고 누적 합 배열을 구한다.
3. (x1,y1), (x2,y2)를 입력받고 해당 구간의 합을 구한다.

 

---

 

 

N이 1024이고, 부분합을 M(100,000) 번 구해야한다.

단순하게 그때 그때 부분합을 구하게 되면 N^2(1024*1024) * M(10만)으로 시간초과가 예상된다.

 

문제는 크게 ① DP[ i ][ j ] 누적합을 만드는 점화식과 ② 문제에서 질문한 넓이를 구하는 점화식으로 나뉘어진다.

 

① DP[ i ][ j ] 누적합을 만드는 점화식

           // (위에↑ 값) + (왼쪽← 값) - (↖중복되는 대각선 값) + (인풋값)
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + map[i][j];

 

DP[ i ][ j ] 를 1,1 부터 i, j까지의 합이라고 가정한다면 쉽게 풀 수 있는 DP문제이다.

 

② 문제에서 질문한 넓이를 구하는 점화식

 

 

 

---

 

 

2차원 배열의 누적 합 계산 방법

 

표는 1행,1열부터 시작이다. 따라서 계산을 위해 생성하는 배열도 인덱스가 1일때 부터 데이터를 저장하고, 인덱스 0의 값은 0인 채로 둔다.
먼저 1행과 1열의 누적 합 부터 구해보자.

• 1행의 누적 합
  S[1][j] = S[1][j-1] + A[1][j]
• 1열의 누적 합
  S[i][1] = S[i-1][1] + A[i][1]
• 그렇다면 2행 2열의 값은 어떻게 계산할까?
  (1,2)까지의 합과 (2,1)까지의 합을 더하고 중복으로 더해진 (1,1)의 값을 뺀 후 (2,2)의 값을 더하면 된다.

같은 방법으로 나머지 누적 합 배열 S의 값을 채울 수 있다.

 

S[ i ][ j ] = S[ i ][ j-1 ] + S[ i-1 ][ j ] - S[ i-1 ][ j-1 ] + A[ i ][ j ]

 

2차원 배열의 구간 합 계산 방법

 

입력 값 2 2 3 4 즉, (2, 2) 부터 (3, 4) 까지의 합을 구하는 경우
(3, 4) 구간 합에서 (1, 4) 구간 합과 (3, 1) 구간 합을 뺀 다음 중복으로 뺀 (1, 1) 구간 합을 더하면 된다.
이런 과정으로 모든 구간 합은 다음과 같은 계산법으로 구할 수 있다.

S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] + S[x1-1][y1-1]

 

Step2. 슈도 코드

N(배열 크기) N(질의 수) 저장하기
for(N만큼 반복하기){
  for(N만큼 반복){
    원본 배열 저장
  }
}
for(N만큼 반복){
  for(N만큼 반복){
    합 배열 저장
    D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1]-[j-1] + A[i][j];
  }
}
for(N만큼 반복){
  질의 계산 및 출력
  결과 = D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1];
}

 

코드

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

public class Main {
    public static void main(String[] args) throws Exception {

        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++){
            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][j - 1] + D[i-1][j] - 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 result = D[x2][y2] - D[x1-1][y2] - D[x2][y1 -1] + D[x1 - 1][y1 -1];
            System.out.println(result);
        }
    }

}