글 읽기 - 시간초과가 발생합니다.

kimthon 4년 전 0

처음 제출 때 시간초과가 나와서 나름 수정을 했는데도 시간초과 에러가 나오네요...

고수님들의 조언이 필요합니다.

나름 고심해서 바꾼 사항은 다음과 같습니다.

* 트리 리스트 관리 -> 트리 덱 관리

* 매 년 정렬 -> 신생 트리를 앞에 위치시킴

* Summer, Fall 부분에 자료를 전부 검색 -> 삭제, 번식 큐를 사용

* 트리 삭제, 번식 큐 -> 트리 포인터 삭제, 번식 큐

#include<iostream>
#include<cstring>
#include<deque>
#include<queue>
#include<algorithm>
using namespace std;

#define START_ENERGY 5
const int UpDown[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };
const int RightLeft[8] = { 0, 1, 1, 1, 0, -1, -1 ,-1 };


class Tree
{
	private:
		int age_, counter_;
		int x_, y_;

	public:
		Tree(int age, int x, int y):age_(age), counter_(age%5),  x_(x), y_(y) {};
		
		bool Aging(int** &map)
		{
			int &energy = map[y_][x_];
			if(age_ <= energy)
			{
				energy -= age_++;
				if(++counter_ == 5) counter_ = 0;
				return true;
			}
			return false;
		}

		bool  CanItSeeding() { return counter_ == 0; }
		void ToEnergy(int** &map) { map[y_][x_] += age_/2; }

		int getAge() { return age_; }
		int getX() { return x_; }
		int getY() { return y_; }
};

bool Cmp(Tree *a, Tree *b) { return b->getAge() > a->getAge(); }

class Map
{
	private:
		int** energy_map_ = NULL;
		int** add_energy_map_ = NULL;
		int size_;
		deque<Tree*> forest;
		queue<Tree*> DQ, SQ;

		void DeleteMap(int** &energy_map)
		{
			if(energy_map == NULL) return;

			for(int y = 0; y < size_; ++y) delete energy_map[y];
			delete energy_map;

			energy_map = NULL;
		}

		void MakeMap(int** &energy_map)
		{
			if(energy_map != NULL) DeleteMap(energy_map);
			
			energy_map = new int*[size_];
			for(int y = 0; y < size_; ++y)
			{
				energy_map[y] = new int[size_];
				for(int x = 0; x < size_; ++x) energy_map[y][x] = 5;
			}
		}

		//양분 흡수
		void Spring()
		{
			for(auto i = forest.begin(); i != forest.end();)
			{
				if(!(*i)->Aging(energy_map_))
				{
					DQ.push(*i);
					i = forest.erase(i);
				}
				else
				{
					if((*i)->CanItSeeding()) SQ.push(*i);
					++i;
				}
			}
		}

		//죽은 나무를 양분으로
		void Summer()
		{	
			while(!DQ.empty())
			{
				auto i = DQ.front();
				i->ToEnergy(energy_map_);
				delete i;
				DQ.pop();
			}
		}

		//번식
		void Fall()
		{
			while(!SQ.empty())
			{
				auto i = SQ.front();
				int x = i->getX();
				int y = i->getY();

				for(int arrow = 0; arrow < 8; ++arrow)
				{
					int tmpX = x + RightLeft[arrow];
					int tmpY = y + UpDown[arrow];

					if(!RangeCheck(tmpX)) continue;
					if(!RangeCheck(tmpY)) continue;

					forest.push_front(new Tree(1, tmpX, tmpY));
				}

				SQ.pop();
			}
		}

		//양분 추가
		void Winter()
		{
			for(int y = 0; y < size_; ++y)
				for(int x = 0; x <size_; ++x)
					energy_map_[y][x] += add_energy_map_[y][x];
		}

		inline bool RangeCheck(int num)
		{
			if(num < 0) return false;
			if(size_ <= num) return false;
			return true;
		}
	public:
		Map(int size):size_(size)
		{
			MakeMap(energy_map_);
			MakeMap(add_energy_map_);
		}

		void setAddEnergyMap()
		{
			for(int y = 0; y < size_; ++y)
				for(int x = 0; x < size_; ++x)
					cin >> add_energy_map_[y][x];
		}

		void setTree(int &x, int &y, int &age) { forest.push_back(new Tree(age,  x - 1, y - 1)); }
		void Sort() { sort(forest.begin(), forest.end(), Cmp); }

		void AfterYear()
		{
			Spring();
			Summer();
			Fall();
			Winter();
		}

		int TreeNum() { return forest.size(); }

		~Map()
		{
			DeleteMap(energy_map_);
			DeleteMap(add_energy_map_);
		}
};


int main()
{
	int size, treeSize, years;
	cin >> size >> treeSize >> years;

	Map map(size);
	map.setAddEnergyMap();
	map.Sort();

	for(int i = 0; i < treeSize; ++i)
	{
		int x, y, z;
		cin >> y >> x >> z;
		map.setTree(x, y, z);
	}

	for(int y = 0; y < years; ++y) map.AfterYear();

	cout << map.TreeNum() << '\n';

	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과가 발생합니다.

kimthon 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말