[백준 / C++] 11660번: 구간 합 구하기 5

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

11660번: 구간 합 구하기 5

난이도: solved.ac 실버 1

 

알고리즘 분류

다이나믹 프로그래밍 (dp), 누적 합 (prefix sum)

 

접근 방법

각 행 별로 1열부터의 누적 합으로 배열에 저장한다.

Ex. sum[3][5] = (3,1)부터 (3,5)까지의 합

      sum[4][7] = (4,1)부터 (4,7)까지의 합

 

그리고 x1, y1, x2, y2를 입력받아 (x1, y1)부터 (x1, y2)까지의 합 + (x1 + 1, y1)부터 (x1 + 1, y2)까지의 합 + ... + (x2, y1)부터 (x2, y2)까지의 합을 계산해 출력한다.

 

코드

#include <bits/stdc++.h>
using namespace std;
int sum[1025][1025];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int N, M, num, i, j;
	cin >> N >> M;
	for (i = 1; i <= N; i++) {
		for (j = 1; j <= N; j++) {
			cin >> num;
			sum[i][j] += (sum[i][j - 1] + num);
		}
	}
	int x1, y1, x2, y2;
	while (M--) {
		int ans = 0;
		cin >> x1 >> y1 >> x2 >> y2;
		for (i = x1; i <= x2; i++)
			ans += (sum[i][y2] - sum[i][y1 - 1]);
		cout << ans << "\n";
	}
}

 

성능

코드 제출 결과

첫 번째로 제출한 것이 내 풀이고 두 번째로 제출한 것은 여기에 소개하지 않은 책의 풀이를 참고한 것이다.

첫 번째는 두 번째에 비해 메모리가 더 적게 든다는 장점이 있지만 시간이 더 오래 걸린다.