본문 바로가기
Algorithm/Baekjoon

11660_구간 합 구하기 5

by 모너아링 2023. 1. 11.

▶실버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