[BOJ 2167] 2차원배열의 합 구하기

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

#include <iostream> #define MAX 301 int N,M,K; int dp[MAX][MAX]; using namespace std; void getSum(){ int value; cin>>N>>M; for(int i=1;i<=N;i++){ for(int j=1;j<=M;j++){ cin>>value; dp[i][j]=value + dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1]; } } cin>>K; while(K--){ int x1,y1,x2,y2; cin>>x1>>y1>>x2>>y2; cout<<dp[x2][y2] -(dp[x1-1][y2] + dp[x2][y1-1] - dp[x1-1][y1-1])<<endl; } } int main(){ getSum(); return 0; }

차근차근 생각하면 어렵지 않은 문제 

어렵다면 그림을 그려보자

dp[i][j]를 구할때 중복되는 값이 있다는 것을 인지한다면 쉽게 풀 수 있다.