[백준 2167] 2차원 배열의 합 (C#, C++) - soo:bak

문제 링크

2167번 - 2차원 배열의 합

설명

N×M 배열과 K개의 직사각형 구간이 주어질 때, 각 구간의 원소 합을 출력합니다. 원소 값은 절댓값 10000 이하이며, 합은 2^31−1 이하입니다.

접근법

(1,1)부터 각 위치까지의 합을 미리 구해두면 직사각형 구간의 합을 빠르게 계산할 수 있습니다.

예를 들어 (2,2)부터 (3,4)까지의 합을 구하려면, (1,1)~(3,4) 전체 합에서 위쪽 영역 (1,1)~(1,4)와 왼쪽 영역 (1,1)~(3,1)을 뺍니다.

이때 (1,1)~(1,1) 부분이 두 번 빠지므로 한 번 다시 더해줍니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var first = Console.ReadLine()!.Split();
    var n = int.Parse(first[0]);
    var m = int.Parse(first[1]);

    var ps = new int[n + 1, m + 1];
    for (var i = 1; i <= n; i++) {
      var parts = Console.ReadLine()!.Split();
      for (var j = 1; j <= m; j++) {
        var v = int.Parse(parts[j - 1]);
        ps[i, j] = v + ps[i - 1, j] + ps[i, j - 1] - ps[i - 1, j - 1];
      }
    }

    var k = int.Parse(Console.ReadLine()!);
    for (var t = 0; t < k; t++) {
      var q = Console.ReadLine()!.Split();
      var i = int.Parse(q[0]);
      var j = int.Parse(q[1]);
      var x = int.Parse(q[2]);
      var y = int.Parse(q[3]);
      var sum = ps[x, y] - ps[i - 1, y] - ps[x, j - 1] + ps[i - 1, j - 1];
      Console.WriteLine(sum);
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m; cin >> n >> m;
  vvi ps(n + 1, vi(m + 1, 0));
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      int v; cin >> v;
      ps[i][j] = v + ps[i - 1][j] + ps[i][j - 1] - ps[i - 1][j - 1];
    }
  }

  int k; cin >> k;
  while (k--) {
    int i, j, x, y; cin >> i >> j >> x >> y;
    int sum = ps[x][y] - ps[i - 1][y] - ps[x][j - 1] + ps[i - 1][j - 1];
    cout << sum << "\n";
  }

  return 0;
}