[백준] 11660_구간 합 구하기5 - JAVA

2차원 배열 구간 합

일단 1차원 배열의 구간 합부터 이해해야한다.

[백준] 11659_구간 합 구하기4 - JAVA

 

2차원 배열의 구간 합은 어려운 거 같으면서도 이해하면 쉽다. 일단 문제의 예시로 설명해보자. 

위 원본 배열을 A라 하자. 원본 배열의 크기가 +1 된 이유는 구간 합 배열의 크기와 똑같이 만들어주기 위함이다. 이 A의 합 배열(S)을 채워보자. 

배경색이 있는 곳이 시작점이다.

for문의 시작 인덱스는 0이 아닌 1이다. index 계산 시 0부터 시작이면 0-1이 되어버리기 때문이다. 아무튼 제일 첫 번째 값을 넣는 건 굳이 계산하지 않아도 '1'이 들어갈 것이라고 유추할 수 있다.

그 다음 배열 자리엔 S[1,1]의 값인 1과 A[1,1]의 값인 2를 더한 값이 들어가야한다. 이런식으로 테두리를 채워보면 아래와 같다.

그럼 이제 어려워 보이는 저 부분에 들어갈 값을 구해보자. 헷갈릴까봐 잘라왔다.

저 주황색 칸 기준으로 왼쪽 칸의 값 + 윗쪽 칸의 값 - 중복된 대각선 칸의 값 + 원본 주황색 칸의 값으로 안에 들어갈 값을 계산할 수 있다. 중복된 대각선이란 주황색 칸 왼쪽, 윗쪽 칸은 구간 합 계산이 되어있는 값이기 때문에 1이 총 두 번 계산되어 중복되었다고 표현했다... 좀 더 프로그래밍적으로 정리해보자면...

구간 합 배열 채우는 공식

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

위 공식으로 구간 합 배열을 채우면 아래와 같이 완성된다.

구간 합 배열 S

구간 합 배열을 완성했으니 이제 그 다음 단계로 나아가야한다. 그 다음 단계는 4개의 숫자를 입력받아 해당 범위의 구간 합을 구하는 일이다. 예제와 똑같이 '2 2 3 4'를 받았다고 치자.

저 범위의 구간 합을 구하면 된다. 이 방법도 구간 합 배열을 채울때와 비슷하다. 일단 S[1,1]부터 S[3,4]의 구간합은 42이다. 그리고 우리가 구하고자 하는 범위는 위와 같다. 그림으로 보자면 아래와 같다.

두 범위가 겹치지 않는 S[1,4], S[3,1]의 구간합을 S[3,4] 구간합에 빼주면 된다.

다만 S[1,1]은 S[1,4]와 S[3,1] 구간 합 계산에 모두 쓰였으므로 계산이 중복되었다. 구간 합을 채울 때와는 다르게 중복된 값을 두 번 소실했으니 한 번 채워줘야한다. 그래서 결론은 42 - 10 - 6 + 1 = 27이 된다. 이것 또한 프로그래밍적으로 나타내보자면...

구간 합을 구하는 공식

result = S[X2][Y2] - S[X1-1][Y2] - S[X2][Y1-1] +S[X1-1][Y1-1]

 

백준_11660

11660번: 구간 합 구하기 5

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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 size = Integer.parseInt(st.nextToken());
        int qCnt = Integer.parseInt(st.nextToken());

        int arr[][] = new int[size+1][size+1];

        for(int i = 1; i <= size; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j <= size; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int sumArr[][] = new int[size+1][size+1];
        for(int i = 1; i <= size; i++) {
            for(int j = 1; j <= size; j++) {
                sumArr[i][j] = sumArr[i][j-1] + sumArr[i-1][j] - sumArr[i-1][j-1] + arr[i][j];
            }
        }

        for(int i = 0; i < qCnt; 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 = sumArr[x2][y2] - sumArr[x1-1][y2] - sumArr[x2][y1-1] + sumArr[x1-1][y1-1];
            System.out.println(result);
        }
    }
}

 

제출 결과

 

이번 문제는 구현보다.. 문제 자체를 이해하는 게 더 어려웠던 거 같다..수포자의 설움