BOJ11660 구간 합 구하기 5

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

N x N개의 수가 N x N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구한다.

누적합

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

제출 코드

BOJ02167 2차원 배열의 합 (opens new window) 이전에 풀었던 문제와 거의 유사하게 풀이하였다.

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

import java.util.Scanner;

public class BOJ11660 {

    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][n + 1];

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

        StringBuilder stringBuilder = new StringBuilder();
        while (m-- > 0) {
            int x1 = scanner.nextInt();
            int y1 = scanner.nextInt();
            int x2 = scanner.nextInt();
            int y2 = scanner.nextInt();

            int result = 0;
            for (int i = x1; i <= x2; i++) {
                result += array[i][y2] - array[i][y1 - 1];
            }

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

        System.out.println(stringBuilder);
    }
}

다이나믹 프로그래밍

DP를 활용한 풀이이다.

제출 코드

import java.util.Scanner;

public class Main {

    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][n + 1];

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

        StringBuilder stringBuilder = new StringBuilder();
        while (m-- > 0) {
            int x1 = scanner.nextInt();
            int y1 = scanner.nextInt();
            int x2 = scanner.nextInt();
            int y2 = scanner.nextInt();

            int result = dp[x2][y2] + dp[x1 - 1][y1 - 1] - dp[x1 - 1][y2] - dp[x2][y1 - 1];

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

        System.out.println(stringBuilder);
    }
}

#BOJ #누적합