BOJ02167 2차원 배열의 합

https://www.acmicpc.net/problem/2167 (opens new window)

2차원 배열이 주어졌을 때 (i, j) 위치 부터 (x, y) 위치까지에 저장되어 있는 수들의 합을 구해야 한다.

누적합

누적합 (Prefix Sum, Cumulative Sum) (opens new window)

제출 코드

누적합을 활용하여 풀이하였다.

문제에서 제시된 배열이다. 각 row별 누적합을 더하여 저장한다.

1 2 4
8 16 32

// 누적합
1 3 7
8 24 56

만약 (1, 1) ~ (2, 3)의 경우 (1, 1) ~ (1, 3), (2, 1) ~ (2, 3)으로 표현이 가능하다. 즉 각 row의 구간합을 구하여 모두 더해주면 저장되어 있는 수들의 합을 구할 수 있다.

아래는 최종 제출 코드이다.

import java.util.Scanner;

public class BOJ2167 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[][] array = new int[n + 1][m + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                array[i][j] = array[i][j - 1] + scanner.nextInt();
            }
        }

        StringBuilder stringBuilder = new StringBuilder();
        int t = scanner.nextInt();
        while (t-- > 0) {
            int i = scanner.nextInt();
            int j = scanner.nextInt();
            int x = scanner.nextInt();
            int y = scanner.nextInt();

            int result = 0;
            for (int a = i; a <= x; a++) {
                result += array[a][y] - array[a][j - 1];
            }

            stringBuilder.append(result).append("\n");
        }

        System.out.println(stringBuilder);
    }
}

다이나믹 프로그래밍

이 문제는 DP를 활용한 풀이도 가능하다.

만약 (3, 3) 까지의 합을 구하기 위해서는 (2, 3)까지의 합과 (3, 2)까지의 합을 더한 뒤, 중복하여 더해지는 (2, 2)까지의 합을 빼서 구할 수 있다. 이것을 코드로 표기하면 아래와 같다.

// array[3][3]는 3, 3에 위치한 값
dp[3][3] = array[3][3] + dp[2][3] + dp[3][2] - dp[2][2];

이것은 2차원 배열을 그림으로 표기하면 더욱 쉽게 이해가 가능하다. 중복되는 부분을 한 번 빼주어 필요한 누적합을 DP를 활용하여 구한다.

이제 특정 구간 좌표의 합을 구해야 한다. 이것 또한 그림을 보면 쉽게 이해가 가능하다.

(i, j) ~ (x, y)의 합을 구하기위해서는 불필요한 부분을 빼준다. 하지만 dp[i - 1][j - 2]까지의 합이 두 번 빠지기 때문에 한 번 더해서 보충한다. 아래는 코드로 표현한 것이다.

dp[x][y] + dp[i - 1][j - 1] - dp[i - 1][y] - dp[x][j - 1];

제출 코드

아래는 최종 제출 코드이다.

import java.util.Scanner;

public class BOJ2167 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[][] dp = new int[n + 1][m + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = scanner.nextInt() + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
            }
        }

        StringBuilder stringBuilder = new StringBuilder();
        int t = scanner.nextInt();
        while (t-- > 0) {
            int i = scanner.nextInt();
            int j = scanner.nextInt();
            int x = scanner.nextInt();
            int y = scanner.nextInt();

            int result = dp[x][y] + dp[i - 1][j - 1] - dp[i - 1][y] - dp[x][j - 1];

            stringBuilder.append(result).append("\n");
        }

        System.out.println(stringBuilder);
    }
}

#BOJ #구현 #누적합