[백준] 11660번 구간 합 구하기5 C++ 풀이

---

알고리즘 분류

• 다이나믹 프로그래밍
• 누적합

---

문제 설명

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.

예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

1	2	3	4
2	3	4	5
3	4	5	6
4	5	6	7

여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.

표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

---

입력 설명

첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)

---

출력 설명

총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.

---

예제 입력

4 3
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
2 2 3 4
3 4 3 4
1 1 4 4

2 4
1 2
3 4
1 1 1 1
1 2 1 2
2 1 2 1
2 2 2 2

---

예제 출력

27
6
64

1
2
3
4

---

아이디어

값을 입력 받는 동시에 누적합도 계산한다.

이후 범위에 따라서 앞의 누적합에서 뒤의 누적합을 빼는걸 행별로 반복하여 합하여 출력한다.

---

알고리즘

값을 입력 받는 동시에 1열부터 시작하는 누적합도 함께 계산한다.

y1 ~ y2의 합을 계산하고 싶다면 (y2까지의 누적합) - (y1-1까지의 누적합)을 계산한다.

이를 행마다 반복하여 총합을 출력한다.

---

코드

#include <iostream>
#include <vector>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin>>n>>m;
	vector<vector<int>> arr(n+2, vector<int>(n+2,0));
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=n; j++)
		{
			cin>>arr[i][j];
			arr[i][j] += arr[i][j-1];
		}
	}
	while(m--)
	{
		int x1,y1,x2,y2,sum=0;
		cin>>x1>>y1>>x2>>y2;
		for(int i=x1; i<=x2; i++)
			sum += arr[i][y2] - arr[i][y1-1];
		cout<<sum<<"\n";
	}
	return 0;
}

---

후기

문제 링크 -> https://www.acmicpc.net/problem/11660

처음에는 모든 행과 열의 누적 합을 계산하여 저장하는 4차원 배열을 사용하는 DP를 사용해서 풀었다.

원하는 출력은 나왔지만 4차원 배열을 사용하므로 메모리 사용이 매우 커서 결국 메모리 초과로 인해 통과하지는 못했다.

이후 3차원 배열을 사용하는 방법으로도 줄였지만 메모리 초과가 나오는 것은 마찬가지였다.

그러다가 입력 받는 동시에 누적 합을 계산하는 방법을 발견하고 쉽게 풀 수 있었다.

---

본 블로그의 모든 글은 개인적인 학습 내용이므로 다양한 오류가 있을 수 있습니다.

오류를 발견하신다면 해당 내용 댓글로 알려주시면 감사하겠습니다!