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

문제 

https://www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

시간 제한 : 1초 (100,000,000)

표의 크기(N) : 1024

합을 구해야 하는 횟수(M) : 100,000

(x, y) : x 는 행, y는 열을 의미한다.

질의마다 문제를 풀었을 때 시간 제한에 걸리기 때문에 배열의 누적 합을 이용해 미리 배열을 만들어 놓고 문제를 푸는 방향으로 잡았다.

문제 풀이

문제에서 요구하는 정답은 (x1, y1)과 (x2, y2)가 주어졌을 때 (x1, y1), (x2, y2)에 해당하는 요소들의 합을 구해야 한다.

문제에서의 예시로 문제를 푼다면 풀이 방향은 다음과 같다.

N = 4

(x1, y1) = (2,2)

(x2, y2) = (3,4)

(1) - (1, 1)부터 (x2, y2)까지 합을 구한다.

(2) - (1, 1)부터 ((x1 - 1), y2)까지 합을 구한 뒤 (1)에서 구한 값에서 뺀다.

(3) - (1, 1)부터 (x2, (y1 - 1))까지 합을 구한 뒤 (1)에서 구한 값에서 뺀다.

(4) - (2), (3)을 진행하면서 (1, 1)에서 ((x1 - 1), (y1 - 1))까지의 값이 두 번 빼기 연산이 들어갔으므로 한 번 더해준다.

 

이대로 누적 합까지 적용해보자.

일단 배열의 누적 합을 구하는 방법은 다음과 같다.

# 해당 배열의 구간 합 구하기
sumArr[x3][y3] = arr[x3][y3] + sumArr[x3 - 1][y3] + sumArr[x3][y3 - 1] - sumArr[x3 - 1][y3 - 1]

위의 방법으로 배열을 완성하면 다음과 같다.

이제 처음 문제 풀이 방법으로 설명했던 그림을 보며 문제를 확인해보자.

표를 비교해서 보니 파란 색으로 진하게 칠 한 (4, 3)은 (1)에서 설명하는 (1, 1)에서부터 (4, 3)까지 합한 것과 같으며,

그리고 빨간 색으로 진하게 칠 한 (1, 3)와 (4, 1)은 (2)와 (3)과 같다는 것을 알 수 있다.

이 사실을 이용해 result를 구해보면 result = (4, 3) - (1, 3) - (4, 1) + (1, 1) = 42 - 6 - 10 + 1 = 27로 문제 예시에서 요구한 정답과 일치한다.

 

이것을 공식으로 나타내면 다음과 같다.

# (x1, y1) 부터 (x2, y2)까지 구간 합 구하기
result = sumArr[x2][y2] - sumArr[x1 - 1][y2] - sumArr[x2][y1 - 1] + sumArr[x1 - 1][y1 - 1]

코드

코드 1.

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 n = Integer.parseInt(st.nextToken());
        // 질의
        int m = Integer.parseInt(st.nextToken());

        int[][] arr = new int[n + 1][n + 1];
        int[][] sumArr = 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++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 배열 누적 합 구하기
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                sumArr[i][j] = arr[i][j] + sumArr[i - 1][j] + sumArr[i][j - 1] - sumArr[i - 1][j - 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());

            int result =
                    sumArr[x2][y2] - sumArr[x2][y1 - 1] - sumArr[x1 - 1][y2] + sumArr[x1 - 1][y1 - 1];
            System.out.println(result);
        }
        br.close();
    }
}

코드 2.

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 n = Integer.parseInt(st.nextToken());
        // 질의
        int m = Integer.parseInt(st.nextToken());
        // 누적 합 배열
        int[][] sumArr = new int[n + 1][n + 1];
        int temp = 0;

        // 따로 배열에 저장하지 않고, 받자 마자 누적합 구하기
        for (int i = 1; i <= n; i++){
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= n; j++) {
                temp = Integer.parseInt(st.nextToken());
                sumArr[i][j] = temp + sumArr[i - 1][j] + sumArr[i][j - 1] - sumArr[i - 1][j - 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());

            int result =
                    sumArr[x2][y2] - sumArr[x2][y1 - 1] - sumArr[x1 - 1][y2] + sumArr[x1 - 1][y1 - 1];
            System.out.println(result);
        }
        br.close();
    }
}