백준 16235번 _나무 재테크

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

16235번: 나무 재테크

 

1. 풀이방법

 

 이 문제는 구현이 어렵다기보단 구현을 하기전 어떤 자료형을 쓸것인지에 대해서 많은 고민이 되는 문제였다.

 

 처음에는 양분에 대한 배열, 겨울에 추가할 양분에 대한 배열, 나무의 개수에 대한 배열, 나무의 데이터에 대한 map

다 따로 만들어 풀었다. 

 하지만, 계속된 시간초과로 인해 인터넷을 참고해 나무의 개수, 나무의 데이터를 합친 vector<int>map[][]이런 형태의 자료형으로 바꾸었다.

 

 그리고 나서는 봄과 여름을 같이 구현하고 가을과 겨울을 한 반복문 안에 구현하여 시간을 줄이는데 최선을 다했다.

 

 1) 첫번째 풀때의 자료형 형태

int foodInFarm[12][12];
int planOfAddedFood[12][12];
int treeInFarm[12][12];
map<pair<int, int>, vector<int>> treeData;
int n, m, k;

 

 2) 시간초과가 나서 바꾼 자료형 형태

int foodInFarm[12][12];
int planOfAddedFood[12][12];
vector <int> treeData[12][12];
int n, m, k;

 

---

 

2. 코드

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

int foodInFarm[12][12];
int planOfAddedFood[12][12];
vector <int> treeData[12][12];
int n, m, k;

void foodInFarmInit()
{
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			foodInFarm[i][j] = 5;
}

void springAndSummer(int y, int x)
{
	vector<int> tmp;
	sort(begin(treeData[y][x]), end(treeData[y][x]));
	int dieTree = 0;
	for (int i = 0; i < (int)treeData[y][x].size(); i++)
	{
		//봄
		int treeYear = treeData[y][x][i];
		if (foodInFarm[y][x] >= treeYear)
		{
			foodInFarm[y][x] -= treeYear;
			tmp.push_back(treeYear + 1);
		}
		//여름 
		else
		{
			dieTree += (treeYear / 2);
		}
	}
	treeData[y][x].clear();
	treeData[y][x] = move(tmp);
	foodInFarm[y][x] += dieTree;
}

/*
--   -0  -+
0-  00  0+
+- +0 ++
*/

int dy[] = { -1, -1, -1, 0,  0, 1, 1, 1 };
int dx[] = { -1,  0,   1, -1, 1,-1, 0, 1 };
void fall(int y, int x)
{
	for (int i = 0; i < 8; i++)
	{
		int fy = y + dy[i];
		int fx = x + dx[i];

		if(fy >=1 && fx >=1 && fy<=n && fx<=n)
			treeData[fy][fx].push_back(1);
	}
}

void winter(int y, int x)
{
	foodInFarm[y][x] += planOfAddedFood[y][x];
}

void oneYear()
{
	//spring and summer
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (treeData[i][j].size() == 0)
				continue;
	
			//봄 여름ㄱㄱ
			springAndSummer(i, j);
		}
	}

	//fall and winter
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (treeData[i][j].size() != 0)
			{
				for (int k = 0; k < (int)treeData[i][j].size(); k++)
				{
					if (treeData[i][j][k] % 5 == 0)
					{
						fall(i, j);
					}
				}
			}
			//winter
			winter(i, j);
		}
	}
}

int countTree()
{
	int cnt = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
				cnt += treeData[i][j].size();
	return cnt;
}

int main()
{
	cin >> n >> m >> k;
	foodInFarmInit();
	int value;
	for(int i =1; i<=n; i++)
		for (int j = 1; j <= n; j++)
		{
			cin >> value;
			planOfAddedFood[i][j] = value;
		}

	int y, x, z;
	for (int i = 0; i < m; i++)
	{
		cin >> y >>x >> z;
		treeData[y][x].push_back(z);
	}

	//봄, 여름, 가을, 겨울
	for(int i=0; i<k; i++ )
	{
		oneYear();
	}

	//살아남은 tree수
	cout << countTree();

	return 0;
}

 

---

 

3. 후기

 

 이 문제 전까지의 구현문제들은 시간에 많은 구애를 받지 않아서 시간복잡도가 빠르게 구현하기보다는 알아보기 쉽게, 고치기 쉽게 구현해왔다. 

 그런데 이 문제는 시간까지 생각해야하니까 구현난이도는 저번문제보다 훨씬 쉬웠지만 나에게는 오히려 더 까다로운 문제였다. 거기다가 찾기힘든 사소한 실수까지 겹치는 바람에 나무공포증이 생길뻔한 문제였다. ㅠ