백준 2167번 : 2차원 배열의 합

  음.... 이거 이렇게 풀어도 되는걸까? 싶은 문제였다. 당연히 시간 초과를 예상하고 제출했는데 왠걸? 그냥 통과됐다. ??? 뭐지? 만우절 장난인가?

 

  진짜 별거없이 O(NMK)의 알고리즘으로 돌렸다. 하나 힘들었던 것은 문제에서 i, j, x, y를 이미 사용하고 있어서 for문 돌릴 때 다른 문자를 사용해야 했다는 점.... ㅋㅋㅋ

 

#include <stdio.h>
#include <iostream>
 
using namespace std;

int n, m;
int arr[300][300];

int sum(int i, int j, int x, int y)
{
    int total = 0;
    
    for(int a = 0; a < n; a++)
    {
        for(int b = 0; b < m; b++)
        {
            if(i <= a && a <= x && j <= b && b <= y) total += arr[a][b];
        }
    }
    
    return total;
}

int main()
{
    cin >> n >> m;
    
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            cin >> arr[i][j];
        }
    }
    
    int k;
    cin >> k;
    
    for(int a = 0; a < k; a++)
    {
        int i, j, x, y;
        cin >> i >> j >> x >> y;
        
        cout << sum(i - 1, j - 1, x - 1, y - 1) << "\n";
    }
 
    return 0;
}