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

#문제

11660번: 구간 합 구하기 5

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

11660번: 구간 합 구하기 5

 

---

#접근방법

n*n의 배열에 숫자값이 있을 때, (x1,y1), (x2,y2)의 좌표가 들어오면 O(1)번만에 정답을 구해야 시간초과가 걸리지 않는다.

 

누적합을 시킨 뒤, 적절한 연산을 해주면 쉽게 풀 수 있다.

반응형

---

#풀이

#include <stdio.h>

int arr[1030][1030];

int main(){
	int n,m;
	int x1,x2,y1,y2;
	
	scanf("%d %d",&n,&m);
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&arr[i][j]);
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			arr[i][j] += arr[i-1][j];
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			arr[i][j] += arr[i][j-1];
	
	for(int i=0;i<m;i++){
		scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
		
		printf("%d\n",arr[x2][y2]-arr[x1-1][y2]-arr[x2][y1-1]+arr[x1-1][y1-1]);
	}
	
	return 0;
}

 

먼저 n*n배열을 입력받고, 각각의 arr[i][j]에 (0,0)부터 (i,j)까지의 누적합을 시켜준다.

 

그리고 (x1,y1), (x2,y2)의 값이 들어오게 되면, 큰 정사각형에 직사각형 2개를 빼준뒤, 중첩되어 빼준 작은 정사각형을 더해주면 (x1,y1) ~ (x2,y2)의 누적값을 구할 수 있다.

 

이를 식으로 옮기면 arr[x2][y2] - arr[x1-1][y2] - arr[x2][y1-1] + arr[x1-1][y1-1]이 된다.

---

#성능

---

#정리

이 문제는 x1 y1 x2 y2의 값이 들어올 때, O(1)의 시간복잡도로 정답을 구할 수 있어야 시간안에 돌아가는 문제였다.

 

이를 해결하기 위해 배열을 누적 합 시켜서 (x1,y1)에서 (x2,y2)까지의 누적합을 구하기 위한 수식을 생각해낼 수 있으면 쉽게 풀 수 있는 문제였다.