[Java] 백준 11660번 문제(구간 합 구하기 5)

원본 링크 : https://www.acmicpc.net/problem/11660

 

문제설명

 

 

소스코드

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

public class Boj_11660
{
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        // n과 m을 받아옴
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        // 구간합 배열 생성
        int[][] sumArr = new int[n + 1][n + 1];
        for(int i = 1; i < n + 1; ++i)
        {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j < n + 1; ++j)
            {
                if(i == 1) sumArr[i][j] = Integer.parseInt(st.nextToken()) + sumArr[i][j - 1];
                else if(j == 1) sumArr[i][j] = Integer.parseInt(st.nextToken()) + sumArr[i - 1][j];
                else sumArr[i][j] = Integer.parseInt(st.nextToken()) + sumArr[i - 1][j] + sumArr[i][j - 1] - sumArr[i - 1][j - 1]; // 핵심 로직 1
            }
        }

        // 구간 합을 통해서 값을 구함
        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());
            sb.append(sumArr[x2][y2] - sumArr[x1 - 1][y2] - sumArr[x2][y1 - 1] + sumArr[x1 - 1][y1 - 1]).append("\n"); // 핵심 로직 2
        }
        System.out.println(sb);
    }
}

 

설명

• 이 문제의 핵심 개념은 누적 합이다.
• 부분합 배열을 이해하려면, 이 배열이 무엇을 하는지부터 이해하는 것이 중요하다. 이 배열은 특정 구간의 합을 빠르게 계산할 수 있도록 도와준다. 이차원 배열에서는 특정 영역의 합을 효율적으로 계산하기 위해 부분합 배열을 사용한다.
• sumArr[i][j] = Integer.parseInt(st.nextToken()) + sumArr[i - 1][j] + sumArr[i][j - 1] - sumArr[i - 1][j - 1];
  각 칸 (i, j)에 해당하는 누적합을 (왼쪽 값 + 위쪽 값 - 대각선 왼쪽 위 값) 방식으로 저장하여, 특정 부분의 합을 O(1) 연산으로 구할 수 있도록 한다.
  sumArr[i - 1][j]: 바로 위쪽 칸까지의 누적합을 더한다.
  sumArr[i][j - 1]: 왼쪽 칸까지의 누적합을 더한다.
  sumArr[i - 1][j - 1]: 위쪽과 왼쪽을 둘 다 포함한 값이 두 번 더해졌으므로 한 번 빼준다.
  현재 위치 (i, j)의 원래 값을 더해주어 최종 누적합을 만든다.
• sumArr[x2][y2] - sumArr[x1 - 1][y2] - sumArr[x2][y1 - 1] + sumArr[x1 - 1][y1 - 1]
  이 공식의 누적 합을 이용하여 구간 합을 계산하는데 사용된다. 각 부분의 의미는 아래와 같다.
  sumArr[x2][y2]: (1,1)부터 (x2,y2)까지의 전체 합
  sumArr[x1 - 1][y2]: 제외해야 할 위쪽 영역
  sumArr[x2][y1 - 1]: 제외해야 할 왼쪽 영역
  sumArr[x1 - 1][y1 - 1]: 위쪽과 왼쪽을 두 번 뺐으므로 한 번 더해줌

 

아직 이해가 되지 않는다면, 아래의 예시를 통해 이해할 수 있다.

1. 누적 합 배열 만들기

 

2. 누적 합 배열을 이용하여 구간 합 계산하기

예를 들어 질의가 2 2 3 4 라면

(3, 4) 구간 합에서 (1, 4) 구간합, (3, 1) 구간 합을 뺀 다음 중복하여 뺀(1, 1) 구간합을 더하면 된다.

 

그림 출처 : Do It! 알고리즘 코딩 테스트 - 자바편