출처 : 백준
문제 보러가기 : 구간 합 구하기5
해당 문제는 n x n의 2차원 배열에 각각의 1000보다 작거나 같은 자연수가 주어질 때 m개의 임의의 (x1,y1), (x2,y2)로 형성되는 사각형 내 포함되는 수들의 합을 구하는 문제이다.
이때 1 ≤ m ≤ 100,000이므로 (x1,y1), (x2,y2)내 인자들을 하나 하나 더하는 방법은 시간초과를 일으킬 수 밖에 없다.
따라서 별도의 n x n의 2차원 배열을 만들어 각각의 자리에 (1,1)부터 (i,j)까지의 합을 누적하여 저장한 후 (x1,y1), (x2,y2)를 입력받으면 누적합 배열에서 계산식을 통해 값을 바로 구하면 간단해지는 문제이다. 설명이 어려우니 그림을 한번 보자
따라서 누적합 (i,j)구간을 구할 때는 sum[i][j] = a[i][j]+sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]이라는 수식을 적용할 수 있다.
또한 n x n의 누적합 배열을 완성한 후 (x1,y1),(x2,y2)구간의 합을 구하는 경우 sum[x2][y2]-(sum[x2][y1-1]+sum[x1-1][y2])+sum[x1-1][y1-1]이라는 수식을 적용할 수 있다.
이처럼 다이나믹 프로그래밍을 이용하여 손쉽게 해당문제를 해결할 수 있다.
소스코드
|
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
34
|
#include <iostream>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, m, x;
int x1, x2, y1, y2;
int sum[1025][1025];
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
cin >> x;
sum[i][j] = x + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
}
}
for (int i = 0; i < m; i++)
{
cin >> x1 >> y1 >> x2 >> y2;
cout << sum[x2][y2] - (sum[x1 - 1][y2] + sum[x2][y1 - 1]) + sum[x1 - 1][y1 - 1] << "\n";
}
return 0;
}
|
cs |
댓글