문제
풀이
DP 를 사용하는 문제이다.
우선 2차원 dp 배열을 만들어준다. N이 1024까지 이므로 1025x1025 크기로 설정한다.
1
int arr[1025][1025],dp[1025][1025];
아래의 코드와 같이 dp 배열에는 누적합을 저장해준다.
1
dp[i][j] = dp[i-1][j]+dp[i][j-1] - dp[i-1][j-1]+arr[i][j];
여기서 주의 할 점은 중복해서 더해지는 dp[i-1][j-1]을 빼주는 것이다.
아래의 그림과 같이 파란 부분의 전체 합이 dp[4][2] 이고 빨간 부분의 전체 합이 dp[3][3]이다.
그림과 같이 dp[4][3]의 값을 구하고자 할 때 dp[4][2]와 dp[3][3]을 더하면 dp[3][2]의 값이 중복되는 것을 알 수 있다. 그러므로 dp[i-1][j-1]의 값을 빼주는 것이다.
이제 우리는 (x1, y1) 부터 (x2, y2)의 구간 합을 얻고 싶다. 위에서 구한 dp를 통해 쉽게 구할 수 있다. 우선 아래의 코드를 살펴보자.
1
2
3
4
cin>>x1>>y1;
cin>>x2>>y2;
ans = dp[x2][y2] - dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1];
cout<<ans<<'\n';
위 코드는 구간 합을 구하는 코드이다. 아래의 그림을 통해 쉽게 이해할 수 있다.
- dp[x2][y2]는 전체 영역의 합의 값을 갖는다.
- dp[x1 - 1][y2]는 빨간색 영역과 보라색영역을 합친 값을 갖는다. 전체영역에서 빼준다.
- dp[x2][y1 - 1]은 파란색 영역과 보라색영역을 합친 값을 갖는다. 전체 영역에서 빼준다.
- dp[x1 - 1][y1 - 1]은 보라색 영역의 합의 값을 갖고, 2와 3번에서 중복해서 빼주기 때문에 한번 더해준다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
using namespace std;
int arr[1025][1025],dp[1025][1025];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>arr[i][j];
dp[i][j] = dp[i-1][j]+dp[i][j-1] - dp[i-1][j-1]+arr[i][j];
}
}
int x1,y1,x2,y2;
int ans;
for(int i=0;i<m;i++)
{
cin>>x1>>y1;
cin>>x2>>y2;
ans = dp[x2][y2] - dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1];
cout<<ans<<'\n';
}
return 0;
}
