📢 이번 문제는 [Java/백준 11659] 구간 합 구하기 4 를 먼저 풀어보고 진행하는 것을 추천합니다 😊

문제

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.
예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

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

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

분석

작성해야할 코드를 단계별로 생각해 본다.

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

소스 코드

import java.util.*;
import java.io.*;

public class TestClass {
    public static void main(String[] args) throws IOException {

        // 1. N, M, N*N 배열 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());	// 2차원 배열의 크기
        int M = Integer.parseInt(st.nextToken());	// 구해야하는 구간 합의 수

        // 2. 배열 입력과 동시에 합배열 구하기
        // S[i][j] = S[i][j-1] + S[i-1][j] - S[i-1][j-1] + A[i][j]
        int[][] S = 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++) {
                S[i][j] = S[i][j-1] + S[i-1][j] - S[i-1][j-1] + Integer.parseInt(st.nextToken());
            }
        }

        // 3. 구간 합 구한 후 출력
        // 구간 합 = S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] + S[x1-1][y1-1]
        int result = 0;
        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());
            result = S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] + S[x1-1][y1-1];
            System.out.println(result);
        }
    }
}

풀이 정리

1. 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 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]

Reference

[book] Do it! 알고리즘 코딩 테스트 - 자바 편