[백준 2167] 2차원 배열의 합

www.acmicpc.net/problem/2167

2167번: 2차원 배열의 합

누적합을 사용하여 시간을 줄이는 문제이다.

(i,j)부터 (x,y)까지 다 더해도 상관없긴 하나 tle가 날꺼 같아서 col기준 누적합을 사용했다.

 

i는 시작 row, x는 마지막 row

col기준 누적합을 사용하므로 sum[?][y] - sum[?][j-1]을 해주면 각 row에 대한 합이 나온다.

 

#include <stdio.h>

using namespace std;

int m, n;
int sum[301][301];
int main(void)
{
  scanf("%d%d", &n, &m);

  for (int i = 1; i <= n; i++)
  {
    for (int j = 1; j <= m; j++)
    {
      scanf("%d", &sum[i][j]);
      sum[i][j] += sum[i][j - 1];
    }
  }

  int t;
  scanf("%d", &t);
  for (int i = 0; i < t; i++)
  {
    int start_r, start_c, end_r, end_c;
    scanf("%d%d%d%d", &start_r, &start_c, &end_r, &end_c);

    int tmp = 0;
    for (int j = start_r; j <= end_r; j++)
    {
      tmp += sum[j][end_c] - sum[j][start_c - 1];
    }

    printf("%d\n", tmp);
  }

  return 0;
}