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

3월 23일(목) - 누적 합 (11660번)

11660번: 구간 합 구하기 5

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- 누적 합 관련 문제이며, dp와 같은 형식의 풀이가 예상된다

- M개의 x1,y1,x2,y2를 입력받을때마다 매번 계산하는 과정으로 풀이를하면 시간초과가 예상된다

  따라서 누적 합을 미리 계산해놓은 뒤, 입력받은 x1,y1,x2,y2에 해당하는 구간합을 구하는 방향으로 설정

- 누적 합은 가로방향 / 세로방향으로 나누어서 더해주면서 중복으로 더해지지 않도록 계산

  arr[ i-1 ][ j ] 와 arr[ i ][ j-1 ] 를 각각 나누어서 더해준다

- 큰 정사각형에서 오른쪽 하단의 작은 정사각형의 넓이를 구하려면

  (전체 정사각형 넓이 - 위에 붙은 직사각형의 넓이 - 왼쪽에 붙은 직사각형의 넓이 + 왼쪽 상단의 정사각형의 넓이)

  와 같은 방식으로 구하는 것을 생각해볼 수 있다

- 마찬가지로 (x1,y1) 부터 (x2,y2)사이의 구간 합을 구하려면

  (x2,y2)까지의 누적 합 - (x1-1,y2)까지의 누적 합 - (x2,y1-1까지의 누적 합) + (x1-1,y1-1까지의 누적 합)

  의 방식으로 구할 수 있을 것 이다

 

1) 최초 arr

arr[1][1]	arr[1][2]	arr[1][3]	arr[1][4]
arr[2][1]	arr[2][2]	arr[2][3]	arr[2][4]
arr[3][1]	arr[3][2]	arr[3][3]	arr[3][4]

2) arr[ i ][ j ] = arr[ i ][ j ] + arr[ i - 1 ][ j ];

arr[1][1]	arr[1][2]	arr[1][3]	arr[1][4]
arr[2][1] + arr[1][1]	arr[2][2] + arr[1][2]	arr[2][3] + arr[1][3]	arr[2][4] + arr[1][4]
arr[3][1] + arr[2][1] + arr[1][1]	arr[3][2] + arr[2][2] + arr[1][2]	arr[3][3] + arr[2][3] + arr[1][3]	arr[3][4] + arr[2][4] + arr[1][4]

3) arr[ i ][ j ] = arr[ i ][ j ] + arr[ i ][ j - 1 ];

arr[1][1]	arr[1][2] + arr[1][1]	arr[1][3] + arr[1][2] + arr[1][1]	arr[1][4] + arr[1][3] + arr[1][2] + arr[1][1]
arr[2][1] + arr[1][1]	arr[2][2] + arr[1][2] + arr[2][1] + arr[1][1]	arr[2][3] + arr[1][3] + arr[2][2] + arr[1][2] + arr[2][1] + arr[1][1]	arr[2][4] + arr[1][4] + arr[2][3] + arr[1][3] + arr[2][2] + arr[1][2] + arr[2][1] + arr[1][1]
...	...	...	...

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

1. 2차원배열 N x N 개를 입력받기 위해서 먼저 정의하는 int arr[1025][1025]를 main 함수 안에서 지역변수로 선언

-> 예제2를 입력하는 경우 잘못된 출력값이 나옴

-> main 함수안에서가 아니라, 전역변수로 2차원배열을 선언했더니 예제1과 예제2 모두 제대로된 출력값이 나옴

-> 이유 모르겠음 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

int arr[1025][1025];

int main(void)
{
	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][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] + arr[i][j - 1];
		}
	}

	for (int i = 1; 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;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ