[Baekjoon] 2167번 : 2차원 배열의 합

1. 문제

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

• DP 문제

// 문제
2차원 배열이 주어졌을 때
(i, j) 위치부터 (x, y) 위치까지에 저장되어 있는
수들의 합을 구하는 프로그램을 작성하시오.
배열의 (i, j) 위치는 i행 j열을 나타낸다.

// 입력
첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다.
다음 N개의 줄에는 M개의 정수로 배열이 주어진다.
배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다.
그 다음 줄에는 합을 구할 부분의 개수 K(1 ≤ K ≤ 10,000)가 주어진다.
다음 K개의 줄에는 네 개의 정수로 i, j, x, y가 주어진다
(1 ≤ i ≤ x ≤ N, 1 ≤ j ≤ y ≤ M).

// 출력
K개의 줄에 순서대로 배열의 합을 출력한다. 배열의 합은 231-1보다 작거나 같다.

// 예제 입력 1
2 3
1 2 4
8 16 32
3
1 1 2 3
1 2 1 2
1 3 2 3

// 예제 출력 1
63
2
36

2. 핵심 아이디어

• DP로 구현

3. Python 문제풀이

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
# dp[i][j] = 1, 1부터 (i, j)까지의 부분합
dp = [[0 for i in range(m + 1)] for _ in range(n + 1)]

for i in range(1, n + 1) :
  for j in range(1, m + 1) :
    dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + arr[i-1][j-1]

for _ in range(int(input())) :
  i, j, x, y = map(int, input().split())
  print(dp[x][y] - dp[i-1][y] - dp[x][j-1] + dp[i-1][j-1])

4. Java 문제풀이

import java.util.*;

class Main {
  static int n, m, k, s = 0;
  static int[][] dp;

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    n = sc.nextInt();
    m = sc.nextInt();
    dp = new int[n+1][m+1];

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

    k = sc.nextInt();
    for (int p=0; p<k; p++) {
      s = 0;
      int i = sc.nextInt();
      int j = sc.nextInt();
      int x = sc.nextInt();
      int y = sc.nextInt();

      for (int q=i; q<x+1; q++) {
        for (int r=j; r<y+1; r++) {
          s += dp[q][r];
        }
      }
      System.out.println(s);
    }
  }
}