[C++/BOJ] 11660 : 구간 합 구하기 5 (DP)

 

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

 

 

백준 실버1

그냥 풀었다가 시간초과나길래 뭐지 싶었는데.. dp 문제였다 ㅜㅜ

index 0부터 시작하면 이것저것 귀찮기 때문에 index 1부터 입력을 받으면 편하다

 

 

나의 풀이

#include<iostream>
#include<vector>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	int m;
	int num;
	int dp[1025][1025] = {0,};
	int x1;
	int x2;
	int y1;
	int y2;

	cin >> n >> m;
	for (int i = 1; i <= n; ++i){
		for (int j = 1; j <= n; ++j)
		{
			cin >> num;
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + num - dp[i - 1][j - 1];
		}
	}

	for (int i = 0; i < m; ++i){
		int answer;
		cin >> x1 >> y1 >> x2 >> y2;
		// 그냥 더하면 시간초과 -> dp 이용
		answer = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1 - 1][y1 - 1];
		cout << answer << "\n";
	}
	
	return 0;
}