[백준 / BOJ] C++ 11660 구간 합 구하기 5

11660번: 구간 합 구하기 5

 

문제

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

11660번: 구간 합 구하기 5

 

 

 

풀이

2차원 배열에서 (x1, y1)부터 (x2, y2)의 합을 출력하는 문제다.

가장 먼저 떠오른 생각은 행 별로 누적 합(prefix sum)을 먼저 구하는 것이었다.

이후 x1, y1, x2, y2를 입력받고 각 행별로(x1, ... , x2) 열의 누적 합(sum[y2] - sum[y1 - 1])을 답에 더해줬다.

 

 

코드

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n, m;
  cin >> n >> m;
  vector<vector<int>> sum(n + 1, vector<int>(n + 1, 0));
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      int x;
      cin >> x;
      sum[i][j] = sum[i][j - 1] + x;
    }
  while (m--) {
    int x1, y1, x2, y2, ans = 0;
    cin >> x1 >> y1 >> x2 >> y2;
    for (int i = x1; i <= x2; i++)
      ans += sum[i][y2] - sum[i][y1 - 1];
    cout << ans << '\n';
  }
  return 0;
}