백준 11660번 구간 합 구하기 5 C++ 구현해보기

---

```

백준 11660번 구간 합 구하기 5 C++ 구현해보기

```

 

이번 글을 통해 배워갈 내용

1.  백준 11660번 풀이

---

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

11660번: 구간 합 구하기 5

 

 

 

백준 11660번 구간 합 구하기 5는

난이도 실버 등급의 문제로서

 

최대 1024 * 1024 사이즈의 2차원 배열에서

특정 지점 A부터 B까지의 구간합을 최대 100,000번 시간제한 1초 안에 구하는 문제입니다.

 

먼저

표의 크기 N , 합을 구해야 하는 횟수 M를 입력받고

표를 입력받은 다음

합을 구해야 하는 좌표를 M만큼 입력받습니다.

 

결과는 각 좌표 쌍마다 크기를 출력해주면 됩니다,

---

30분 정도 위에 링크를 방문하셔서 풀어보시고

안 풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.

---

일단 입력을 받습니다.

저의 경우 클래스를 만들어서 활용했습니다.

 

	// 입력 최적화
	std::cin.tie(NULL);
	std::ios::sync_with_stdio(false);

	int32_t boardSize;	
	int32_t testCase;
	std::cin >> boardSize;
	std::cin >> testCase;
	std::cin.ignore();

	std::string inputStr;

	CBoard* cBoard = new CBoard(boardSize, boardSize);
	int32_t tempSum = 0;

	for (int32_t i = 0; i < boardSize; i++)
	{
		std::getline(std::cin, inputStr);
		std::stringstream ss(inputStr);
		int32_t tempNum;
		for (int32_t j = 0; j < boardSize; j++)
		{
			ss >> tempNum;
			tempSum += tempNum;
			cBoard->setBoardElement(i, j, tempNum);
			cBoard->setHSumBoardElement(i, j, tempSum);
		}
	}

예를 들어

4 4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

를 입력받을 경우

 

board는 다음과 같습니다.
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

 

합을 더한 배열을 연습하면서 아래와 같이 만들었고

 

Hsum(수평방향)
1 3 6 10
15 21 28 36
45 55 66 78
91 105 120 136

Vsum(수직방향)
1 30 63 100
6 36 70 108
15 46 81 120
28 60 96 136

 

실질적으로 사용한 건

Dsum 배열입니다.
1 3 6 10
6 14 24 36
15 33 54 78
28 60 96 136

	cBoard->setHSumBoard();
	cBoard->setVSumBoard();
	cBoard->setDSumBoard();

Dsum 배열은

아래와 같이

각 행의 수평 구간 합과 윗행의 구간합 원소를 더해 계산해주었습니다. 

	void setDSumBoard()
	{
		int32_t tempSum = 0;
		for (int32_t j = 0; j < col; j++)
		{
			tempSum += (getBoardElement(0, j));
			setDSumBoardElement(0, j, tempSum);
		}

		tempSum = 0;
		for (int32_t i = 0; i < row; i++)
		{
			tempSum += (getBoardElement(i, 0));
			setDSumBoardElement(i, 0, tempSum);
		}
		
		for (int32_t i = 1; i < row; i++)
		{
			tempSum = 0;
			for (int32_t j = 0; j < col; j++)
			{
				tempSum += getBoardElement(i, j);
				const int32_t tempElem = tempSum + getDSumBoardElement((i - 1), j);
				setDSumBoardElement(i, j, tempElem);
			}
		}
	}

미리 모든 합을 계산해두고

테스트 케이스 입력에 따라서

 

	for (int32_t i = 0; i < testCase; i++)
	{
		std::getline(std::cin, inputStr);
		std::stringstream ss(inputStr);
		int32_t tempNum;
		ss >> tempNum;
		int32_t x1 = tempNum -1;
		ss >> tempNum;
		int32_t y1 = tempNum -1;
		ss >> tempNum;
		int32_t x2 = tempNum -1;
		ss >> tempNum;
		int32_t y2 = tempNum -1;

		int32_t ret;

		if (x1 == x2 && y1 == y2)
		{
			ret = cBoard->getBoardElement(x2, y2);
		}
		else
		{
			ret = cBoard->getDSumBoardElement(x2, y2);
			if (y1 > 0) { ret -= cBoard->getDSumBoardElement(x2, y1 - 1); };
			if (x1 > 0) { ret -= cBoard->getDSumBoardElement(x1 - 1, y2); };
			if (x1 > 0 && y1 > 0) { ret += cBoard->getDSumBoardElement(x1 - 1, y1 - 1); };
		}
		std::cout << ret << "\n";
	}

 

Dsum 배열을 활용해서

예를 들어

board가 다음과 같고
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

(2,2)인 6에서 (4,4)인 16까지 구간합을 구하고자 한다면

 

구간합 예시

노란 부분을 구하고자 한다면

 

초록 부분 136에

빨간 부분 10을 빼고

주황 부분 28을 빼고

주황과 빨강의 겹치는 1을 다시 더해주면 됩니다.

 

 

 

 

 

 

전체 코드는 다음과 같습니다

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <array>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <regex>

class CBoard
{
private:
	int32_t row;
	int32_t col;
	int32_t** board;
	int32_t** hSumBoard;
	int32_t** vSumBoard;
	int32_t** dSumBoard;
public:
	CBoard(const int32_t _row, const int32_t _col)
	{
		this->row = _row;
		this->col = _col;
		board = new int32_t * [_row];
		hSumBoard = new int32_t * [_row];
		vSumBoard = new int32_t * [_col];
		dSumBoard = new int32_t * [_col];

		for (int32_t i = 0; i < _row; i++)
		{
			board[i] = new int32_t[_col];
			hSumBoard[i] = new int32_t[_col];
		}
		for (int32_t i = 0; i < _col; i++)
		{
			vSumBoard[i] = new int32_t[_row];
		}
		for (int32_t i = 0; i < _col; i++)
		{
			dSumBoard[i] = new int32_t[_row];
		}
	}

	~CBoard()
	{
		if (board != nullptr)
		{
			for (int32_t i = 0; i < row; i++)
			{ 
				if (board[i] != nullptr)
				{ 
					delete[] board[i];
				} 
			} 
			delete[] board;
		}

		if (hSumBoard != nullptr)
		{
			for (int32_t i = 0; i < row; i++)
			{
				if (hSumBoard[i] != nullptr)
				{
					delete[] hSumBoard[i];
				}
			}
			delete[] hSumBoard;
		}

		if (vSumBoard != nullptr)
		{
			for (int32_t i = 0; i < col; i++)
			{
				if (vSumBoard[i] != nullptr)
				{
					delete[] vSumBoard[i];
				}
			}
			delete[] vSumBoard;
		}

		if (dSumBoard != nullptr)
		{
			for (int32_t i = 0; i < col; i++)
			{
				if (dSumBoard[i] != nullptr)
				{
					delete[] dSumBoard[i];
				}
			}
			delete[] dSumBoard;
		}
	}

	void setHSumBoard()
	{
		int32_t tempSum = 0;
		for (int32_t i = 0; i < row; i++)
		{
			for (int32_t j = 0; j < col; j++)
			{
				tempSum += getBoardElement(i, j);
				setHSumBoardElement(i, j, tempSum);
			}
		}
	}

	void setVSumBoard()
	{
		int32_t tempSum = 0;
		for (int32_t i = 0; i < col; i++)
		{
			for (int32_t j = 0; j < row; j++)
			{
				tempSum += getBoardElement(j, i);
				setVSumBoardElement(j, i, tempSum);
			}
		}
	}

	void setDSumBoard()
	{
		int32_t tempSum = 0;
		for (int32_t j = 0; j < col; j++)
		{
			tempSum += (getBoardElement(0, j));
			setDSumBoardElement(0, j, tempSum);
		}

		tempSum = 0;
		for (int32_t i = 0; i < row; i++)
		{
			tempSum += (getBoardElement(i, 0));
			setDSumBoardElement(i, 0, tempSum);
		}
		
		for (int32_t i = 1; i < row; i++)
		{
			tempSum = 0;
			for (int32_t j = 0; j < col; j++)
			{
				tempSum += getBoardElement(i, j);
				const int32_t tempElem = tempSum + getDSumBoardElement((i - 1), j);
				setDSumBoardElement(i, j, tempElem);
			}
		}
	}

	void setBoardElement(const int32_t i, const int32_t j, const int32_t elem)
	{
		board[i][j] = elem;
	}

	void setHSumBoardElement(const int32_t j, const int32_t i, const int32_t sum)
	{
		hSumBoard[j][i] = sum;
	}

	void setVSumBoardElement(const int32_t i, const int32_t j, const int32_t sum)
	{
		vSumBoard[i][j] = sum;
	}

	void setDSumBoardElement(const int32_t i, const int32_t j, const int32_t sum)
	{
		dSumBoard[i][j] = sum;
	}

	int32_t getHSumBoardElement(const int32_t i, const int32_t j)
	{
		return hSumBoard[i][j];
	}

	int32_t getVSumBoardElement(const int32_t i, const int32_t j)
	{
		return vSumBoard[i][j];
	}

	int32_t getDSumBoardElement(const int32_t i, const int32_t j)
	{
		return dSumBoard[i][j];
	}

	int32_t getBoardElement(const int32_t i, const int32_t j)
	{
		return board[i][j];
	}

	

	void printBoard()
	{
		std::cout << "\nboard\n";
		for (int i = 0; i < row; i++)
		{
			for (int j = 0; j < col; j++)
			{
				std::cout << board[i][j] << " ";
			}
			std::cout << "\n";
		}
	}

	void printHSumBoard()
	{
		std::cout << "\nHsum\n";
		for (int i = 0; i < row; i++)
		{
			for (int j = 0; j < col; j++)
			{
				std::cout << hSumBoard[i][j] << " ";
			}
			std::cout << "\n";
		}
	}

	void printVSumBoard()
	{
		std::cout << "\nVsum\n";
		for (int i = 0; i < row; i++)
		{
			for (int j = 0; j < col; j++)
			{
				std::cout << vSumBoard[i][j] << " ";
			}
			std::cout << "\n";
		}
	}

	void printDSumBoard()
	{
		std::cout << "\nDsum\n";
		for (int i = 0; i < row; i++)
		{
			for (int j = 0; j < col; j++)
			{
				std::cout << dSumBoard[i][j] << " ";
			}
			std::cout << "\n";
		}
	}

};





int main()
{




	// 입력 최적화
	std::cin.tie(NULL);
	std::ios::sync_with_stdio(false);

	int32_t boardSize;	
	int32_t testCase;
	std::cin >> boardSize;
	std::cin >> testCase;
	std::cin.ignore();

	std::string inputStr;

	CBoard* cBoard = new CBoard(boardSize, boardSize);
	int32_t tempSum = 0;

	for (int32_t i = 0; i < boardSize; i++)
	{
		std::getline(std::cin, inputStr);
		std::stringstream ss(inputStr);
		int32_t tempNum;
		for (int32_t j = 0; j < boardSize; j++)
		{
			ss >> tempNum;
			tempSum += tempNum;
			cBoard->setBoardElement(i, j, tempNum);
			cBoard->setHSumBoardElement(i, j, tempSum);
		}
	}

	cBoard->setHSumBoard();
	cBoard->setVSumBoard();
	cBoard->setDSumBoard();

	//cBoard->printBoard();
	//cBoard->printHSumBoard();
	//cBoard->printVSumBoard();
	//cBoard->printDSumBoard();

	for (int32_t i = 0; i < testCase; i++)
	{
		std::getline(std::cin, inputStr);
		std::stringstream ss(inputStr);
		int32_t tempNum;
		ss >> tempNum;
		int32_t x1 = tempNum -1;
		ss >> tempNum;
		int32_t y1 = tempNum -1;
		ss >> tempNum;
		int32_t x2 = tempNum -1;
		ss >> tempNum;
		int32_t y2 = tempNum -1;

		int32_t ret;

		if (x1 == x2 && y1 == y2)
		{
			ret = cBoard->getBoardElement(x2, y2);
		}
		else
		{
			ret = cBoard->getDSumBoardElement(x2, y2);
			if (y1 > 0) { ret -= cBoard->getDSumBoardElement(x2, y1 - 1); };
			if (x1 > 0) { ret -= cBoard->getDSumBoardElement(x1 - 1, y2); };
			if (x1 > 0 && y1 > 0) { ret += cBoard->getDSumBoardElement(x1 - 1, y1 - 1); };
		}
		std::cout << ret << "\n";
	}


	delete cBoard;

}

 

입력과 결과

4 4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
1 1 2 2
14
2 2 2 2
6
2 2 3 4
54
2 2 4 3
63

 

 

읽어주셔서 감사합니다

 

무엇인가 얻어가셨기를 바라며

 

오늘도 즐거운 코딩 하시길 바랍니다 ~ :)

 

참조 및 인용

C++ Primer

Introduction to Algorithms

---

https://codemasterkimc.tistory.com/35

C++ 이론을 배울수 있는 곳 정리

 

https://codemasterkimc.tistory.com/50

300년차 개발자의 좋은 코드 5계명 (Clean Code)

 

---