[ 백준 11660] 구간 합 구하기 5(C++)

11660번: 구간 합 구하기 5

 

 

문제!

 

---

 

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이다.

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

 

---

이번문제는 1차원 줄이 아닌 표에 누적합을 적용시키는 문제였습니다.

 

차원이 높아졌다고 해서 엄청 어려워졌다! 라는건 아니였습니다!

약간만 생각하시면 쉽게 풀수있을겁니다..

ㄱ ㄱ!

 

 

 

 

일단 누적합을 계산할껀데 이제는 0,0에서 y,x 까지의 합을 저장해줄겁니다.

 

그럼 다음 y+1,x+1은 어떻게 구할까요??

 

dp[y][x]+=dp[y-1][x]+dp[y][x-1]-dp[y-1][x-1] 

 

이해 되시나요..?

 

 

그림으로 그려보면 아래처럼 됩니다.

 

dp[y-1][x]+dp[y][x-1] 으로  넓이를 구해주고 중복된 만큼의 dp[y-1][x-1]  빼준값을 더해준다면 

 

dp[y][x] 의 누적합 넓이를 구할수있습니다!

 

 

 

 

똑같은 원리로 y1,x1 ~ y2,x2 까지의 넓이도 구해낼수있습니다.

 

 

그럼 코드 시작!

---

 

이라고 하기에는 좀 짧네요....

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, M;
	
	cin >> N >> M;

	for (int i = 1; i < N+1; i++) {
		for (int j = 1; j < N+1; j++) {
			cin >> all[i][j];
			all[i][j] += all[i - 1][j] + all[i][j - 1] - all[i - 1][j - 1];
		}
	}

	int x1, y1, x2, y2;


	for (int i = 1; i < M + 1; i++) {
		cin >> y1 >> x1 >> y2 >> x2;

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



	return 0;
}

 

 

넵.... 위에서 설명한 그림대로 짜주시면 됩니다!

 

 

화이팅!

 

 

 

 

ALL

#include <iostream>

using namespace std;


int all[1025][1025] = { 0 };

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, M;
	
	cin >> N >> M;

	for (int i = 1; i < N+1; i++) {
		for (int j = 1; j < N+1; j++) {
			cin >> all[i][j];
			all[i][j] += all[i - 1][j] + all[i][j - 1] - all[i - 1][j - 1];
		}
	}

	int x1, y1, x2, y2;


	for (int i = 1; i < M + 1; i++) {
		cin >> y1 >> x1 >> y2 >> x2;

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



	return 0;
}

 

 

 

 

 

 

틀린점이 있다면 댓 달아주세요!