▶실버1
풀이
누적 합 이용.
0 | 1 | 2 | 3 | 4 | |
0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 1 | 2 | 3 | 4 |
2 | 0 | 2 | 3 | 4 | 5 |
3 | 0 | 3 | 4 | 5 | 6 |
4 | 0 | 4 | 5 | 6 | 7 |
=> 배열 표
0 | 1 | 2 | 3 | 4 | |
0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 1 | 3 | 6 | 10 |
2 | 0 | 3 | 8 | 15 | 24 |
3 | 0 | 6 | 15 | 27 | 42 |
4 | 0 | 10 | 24 | 42 | 64 |
=> 누적 합 표
ex) (2, 2) ~ (3, 4) 의 구간 합
이는 8 + 15 + 24 + 15 + 27 + 42 와 같은데, 누적합을 이용하면
sum[3][4] - sum[3][1] - sum[1][4] + sum[1][1] 임을 알 수 있다.
이를 통하여 (x1, y1) ~ (x2, y2)의 구간 합의 점화식은 sum[x2][y2] - sum[x2][y1 -1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1] 이다.
또, 주의할 점은 x1 == 1 || y1 == 1일 경우에 범위가 벗어나므로 x = 0 || y = 0의 인덱스를 가지는 배열을 0으로 채워준다.(가장 윗 줄과 가장 왼쪽 줄)
코드
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int sum[1030][1030];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
//가장자리 0으로 채우기
if (i == 0 || j == 0) {
sum[i][j] = 0;
continue;
}
int num;
cin >> num;
if (i > 1 && j > 1) {
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + num;
}
else if (i == 1 && j > 1) {
sum[i][j] = sum[i][j - 1] + num;
}
else if (i > 1 && j == 1) {
sum[i][j] = sum[i - 1][j] + num;
}
else {
sum[i][j] = num;
}
}
}
for (int i = 0; i < m; i++) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
int ans = sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1];
cout << ans << "\n";
}
}
'Algorithm > Baekjoon' 카테고리의 다른 글
9465_스티커 (1) | 2023.01.16 |
---|---|
1699_제곱수의 합 (0) | 2023.01.13 |
11055_가장 큰 증가 부분 수열 (0) | 2023.01.10 |
11057_오르막수 (0) | 2023.01.04 |
2003_수들의 합 2 (0) | 2023.01.02 |