[백준 11660] 구간 합 구하기 5 (C#, C++) - soo:bak

문제 링크

11660번 - 구간 합 구하기 5

설명

N × N 크기의 표가 주어지는 상황에서, N (1 ≤ N ≤ 1,024)과 표의 숫자들, 그리고 M (1 ≤ M ≤ 100,000)개의 쿼리가 주어질 때, 각 쿼리마다 (x1, y1)부터 (x2, y2)까지의 직사각형 구간 합을 구하는 문제입니다.

M이 최대 100,000이므로 각 쿼리를 O(1)에 처리해야 하며, 이를 위해 2차원 누적합을 사용합니다.

접근법

2차원 누적합을 전처리하여 각 쿼리를 O(1)에 답합니다.

먼저 prefix[r][c]를 (1, 1)부터 (r, c)까지의 직사각형 합으로 정의합니다. 이를 계산할 때 위쪽과 왼쪽의 누적합을 더하고, 중복으로 더해진 왼쪽 위 대각선 부분을 빼고, 현재 값을 더합니다.

쿼리에 답할 때는 큰 직사각형에서 불필요한 부분을 빼는 방식을 사용합니다. prefix[x2][y2]에서 위쪽과 왼쪽의 불필요한 부분을 빼고, 중복으로 뺀 왼쪽 위 대각선 부분을 다시 더합니다.

이렇게 하면 각 쿼리를 O(1)에 처리할 수 있습니다.

---

Code

C#

using System;
using System.IO;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      using var sr = new StreamReader(Console.OpenStandardInput());
      using var sw = new StreamWriter(Console.OpenStandardOutput());

      var first = Array.ConvertAll(sr.ReadLine()!.Split(), int.Parse);
      var n = first[0];
      var m = first[1];

      var ps = new int[n + 1, n + 1];
      for (var r = 1; r <= n; r++) {
        var row = Array.ConvertAll(sr.ReadLine()!.Split(), int.Parse);
        for (var c = 1; c <= n; c++)
          ps[r, c] = ps[r - 1, c] + ps[r, c - 1] - ps[r - 1, c - 1] + row[c - 1];
      }

      for (var i = 0; i < m; i++) {
        var q = Array.ConvertAll(sr.ReadLine()!.Split(), int.Parse);
        var x1 = q[0];
        var y1 = q[1];
        var x2 = q[2];
        var y2 = q[3];
        var ans = ps[x2, y2] - ps[x1 - 1, y2] - ps[x2, y1 - 1] + ps[x1 - 1, y1 - 1];
        sw.WriteLine(ans);
      }
    }
  }
}

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(n + 1, 0));

  for (int r = 1; r <= n; r++) {
    for (int c = 1; c <= n; c++) {
      int v; cin >> v;
      ps[r][c] = ps[r - 1][c] + ps[r][c - 1] - ps[r - 1][c - 1] + v;
    }
  }

  for (int i = 0; i < m; i++) {
    int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
    int ans = ps[x2][y2] - ps[x1 - 1][y2] - ps[x2][y1 - 1] + ps[x1 - 1][y1 - 1];
    cout << ans << "\n";
  }

  return 0;
}