[Silver I] 구간 합 구하기 5 - 11660

문제 링크

성능 요약

메모리: 11792 KB, 시간: 244 ms

분류

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

제출 일자

2025년 10월 13일 20:32:20

문제 설명

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

제출

// 백준 11660

// - 아이디어
// 구간합 생성, 
// 좌표 사이 덧셈을 위해서 -> 행별 구간합 뺄셈 -> 행 갯수만큼(|y1-y2|) 전부 덧셈
// 
// - 시간복잡도
// 구간합 : N^2
// 
// 행별 구간합 뺄셈 : 상수
// 행 갯수 최악 : N 
// ---> 이걸 M번 진행 : N*M
// 
// N^2+N*M = O(N*M) = 10^8 아슬아슬하다
// 
// - 자료구조
// board : int[N][N]
// 구간합 S : int[N][N]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>

int N, M;
int board[1025][1025];
int S[1025][1025];
int point[100'000][4];

void CalculateSum(int point[4]);
void MakePrefixSum();
int main()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);

	std::cin >> N >> M;

	for (int iY = 1; iY < N+1; iY++)
	{
		for (int iX = 1; iX < N+1; iX++)
		{
			std::cin >> board[iY][iX];
		}
	}

	// 구간합
	MakePrefixSum();

	// 합 계산 및 출력
	
	for (int i = 0; i < M; i++)
	{
		int x1, y1;
		int x2, y2;
		std::cin >> point[i][1] >> point[i][0];
		std::cin >> point[i][3] >> point[i][2];
	}
	
	for (int i = 0; i < M; i++)
	{
		  CalculateSum(point[i]);
	}
	return 0;
}

void CalculateSum(int point[4])
{
	int x1 = point[0];
	int y1 = point[1];
	int x2 = point[2];
	int y2 = point[3];
		
	int diff_Y = abs(y1 - y2);
	int min_Y;
	int min_X;
	int max_X;
	if (y1 < y2) min_Y = y1;
	else min_Y = y2;

	if (x1 < x2)
	{
		min_X = x1;
		max_X = x2;
	}
	else
	{
		min_X = x2;
		max_X = x1;
	}

	int curr_Y = min_Y;
	
	int sum=0;
	for (int i = 0; i < diff_Y + 1; i++)
	{
		if (min_X == 1)
		{
			sum += S[curr_Y][max_X] - S[curr_Y-1][N];
		}
		else
		{
			sum += S[curr_Y][max_X] - S[curr_Y][min_X - 1];
		}
		curr_Y++;
	}

	std::cout << sum << "\n";
}

void MakePrefixSum(){

	for (int iY = 1; iY < N + 1; iY++)
	{
		for (int iX = 1; iX < N + 1; iX++)
		{ 
			if (iX == 1)
			{
				S[iY][iX] = S[iY-1][N] + board[iY][iX];
			}
			else
			{
				S[iY][iX] = S[iY][iX - 1] + board[iY][iX];
			}
		}
	}
}

아쉬운점 및 효율적인 방법

시간 통과는 했으나 굉장히 무식하게 풀었고, 출제의도한 방법론이 아님. 매우 비효율적인 로직

우선 문제의 조건을 제대로 못봄 X1 < X2 등... 잘보도록 하자

그리고 행이 x 열이 y이기 때문에 2차원 배열에서 [x][y]로 구성해야 직관적임

구간합을 1차원로만 인식함, 2차원의 평면 형태로 구간합을 구하는것이 아니고,, 1차원 배열을 한 행씩 모든 행을 더하면서 진행하였음 -> O(M*N) M번마다 최대 N행을 더하는 로직

구간합을 2차원으로 본다면, 존재하는 구간합 자체가 2차원의 구간합(1,1 좌표부터 자기자신까지의 합)을 가지고 있기 때문에 두 좌표가 주어졌을때 X2,Y2 구간합을 구할때 본인 값에서 (X2,Y1-1)과 (X1-1,Y2)을 빼고 이 둘의 공통면(X1-1,Y1-1)을 다시 빼주면 O(1)로 구간합을 구할수있다.

다시풀어볼것