[백준] 구간 합 구하기 5

 

구간 합 구하기 5

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

79351

36213

26847

43.847%

문제

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)까지 합을 구해 출력한다.

---

구간 합을 2차원 배열로 할 수 있어야 풀 수 있는 문제이다.

원래 배열인 origin 배열과 구간합 배열인 add배열이 있을때 구간 합 공식은 이렇다.

add[i][j] = add[i][j-1]+add[i-1][j]-add[i-1][j-1]+origin[i][j]

            = (위쪽) + (왼쪽) - (대각선 왼쪽) + (원래 자리)를 더하면된다.

위 방식으로 합배열을 만든다

 

이후 구간합을 통해 값을 처리한다 구간합 좌표가 [x1,y1] ~ [x2,y2] 까지의 합을 알아보기 위해서는구간 합 구하기 5

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초 256 MB 79351 36213 26847 43.847%

문제

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)까지 합을 구해 출력한다.

---

 

구간 합을 2차원 배열로 할 수 있어야 풀 수 있는 문제이다.

 

원래 배열인 origin 배열과 구간합 배열인 add배열이 있을때 구간 합 공식은 이렇다.

 

add[i][j] = add[i][j-1]+add[i-1][j]-add[i-1][j-1]+origin[i][j]

 

            = (위쪽) + (왼쪽) - (대각선 왼쪽) + (원래 자리)를 더하면된다.

 

위 방식으로 합배열을 만든다

 

 

이후 구간합을 통해 값을 처리한다 구간합 좌표가 [x1,y1] ~ [x2,y2] 까지의 합 공식은

add[x2,y2] - add[x2,y1-1] - add[x1-1][y2] + add[x1-1][y1-1] 이된다

(원래자리) - (위쪽) - (왼쪽) + (대각선 왼쪽)이다

 

#include <iostream>
#include <vector>
using namespace std;

//구간 합 구하기 5 11660
int main()
{

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int m;
	int n;

	cin >> m >> n;

	vector<vector<int>> origin(m + 1, vector<int>(m + 1, 0));
	vector<vector<int>> add(m + 1, vector<int>(m + 1, 0));

	for (int i = 1; i <= m; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> origin[i][j];
			add[i][j] = add[i][j - 1] + add[i - 1][j] - add[i - 1][j - 1] + origin[i][j];
		}
	}

	for (int i = 0; i < n; i++)
	{
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;

		cout << add[x2][y2] - add[x2][y1 - 1] - add[x1 - 1][y2] + add[x1 - 1][y1 - 1]<<"\n";
	}
}

 

vector<vector<int>> origin(m + 1, vector<int>(m + 1, 0));
	vector<vector<int>> add(m + 1, vector<int>(m + 1, 0));

2차원 배열의 길이가 동적으로 할당되어야 하기 때문에 vector를 통해 2차원 vector로 문제를 풀어야 한다.

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