2167번 2차원 배열의 합

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

 

이 문제는 3중 for문으로 풀어도 정답이 인정된다. 그러나 많은 사람들이 dp로 문제를 풀었고 3중 포문으로 풀었으니 나 또한 dp로 풀어보려고 한다.

 

아래는 3중 포문으로 푼 코드인데 실제로 400ms 정도 걸려 오랜 시간이 걸린다.

#include <iostream>
using namespace std;
int num[301][301];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int y, x;
    cin >> y >> x;
    for(int i=1; i<=y; i++)
    {
        for(int j=1; j<=x; j++)
        {
            cin >> num[i][j];
        }
    }
    int k, startY, startX, endY, endX, sum = 0;
    cin >> k;
    for(int i=0; i<k; i++)
    {
        sum = 0;
        cin >> startY >> startX >> endY >> endX;
        for(int q=startY; q<=endY; q++)
        {
            for(int j=startX; j<=endX; j++)
                sum += num[q][j];
        }
        cout << sum << '\n';
    }
    
    return 0;
}

 

dp의 경우 좀 더 생각해보고 코드를 작성해보아야 겠다.