나무 재테크 (feat. 백준, 16235번)

나무 재테크
https://www.acmicpc.net/problem/16235

16235번: 나무 재테크

반응형

// woohyeon.kim
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int N, M, K;
int map[11][11], fertilizer[11][11];
vector<int> alive[11][11];
queue<int> dead[11][11];
int dx[8], dy[8];

inline void sort_alive_tree()
{
	for (int ix = 1, iy; ix <= N; ++ix)
		for (iy = 1; iy <= N; ++iy)
			if (alive[ix][iy].size() > 1)
				sort(alive[ix][iy].begin(), alive[ix][iy].end());
}
inline void spring()
{
	vector<int>::iterator iter;
	for (int ix = 1, iy; ix <= N; ++ix)
		for (iy = 1; iy <= N; ++iy)
			if (!alive[ix][iy].empty())
				for (iter = alive[ix][iy].begin(); iter != alive[ix][iy].end();)
					if (*iter > map[ix][iy]) {
						dead[ix][iy].push(*iter), iter = alive[ix][iy].erase(iter);
					}
					else {
						map[ix][iy] -= *iter, ++(*iter), ++iter;
					}
}

inline void summer()
{
	for (int ix = 1, iy, tree_age; ix <= N; ++ix)
		for (iy = 1; iy <= N; ++iy)
			while (!dead[ix][iy].empty())
				tree_age = dead[ix][iy].front(), dead[ix][iy].pop(), map[ix][iy] += (tree_age / 2);
}

inline void autumn()
{
	for(int ix = 1, iy, index, idx, nx, ny; ix <= N; ++ix)
		for(iy = 1; iy <= N; ++iy)
			if(!alive[ix][iy].empty())
				for(index = 0; index < static_cast<int>(alive[ix][iy].size()); ++index)
					if(alive[ix][iy][index] % 5 == 0)
						for (idx = 0; idx < 8; ++idx) {
							nx = ix + dx[idx], ny = iy + dy[idx];
							if (1 <= nx && nx <= N && 1 <= ny && ny <= N)
								alive[nx][ny].push_back(1);
						}
}

inline void winter()
{
	for (int ix = 1, iy; ix <= N; ++ix)
		for (iy = 1; iy <= N; ++iy)
			if(fertilizer[ix][iy] != 0)		map[ix][iy] += fertilizer[ix][iy];
}

int main()
{
	ios_base::sync_with_stdio(false), cin.tie(), cout.tie();
	for (int ix = 1, iy; ix <= 10; ++ix)
		for (iy = 1; iy <= 10; ++iy)
			fertilizer[ix][iy] = 0, map[ix][iy] = 5;
	cin >> N >> M >> K;
	for (int ix = 1, iy; ix <= N; ++ix)
		for (iy = 1; iy <= N; ++iy)
			cin >> fertilizer[ix][iy];
	for (int idx = 0, x, y, z; idx < M; ++idx)
		cin >> x >> y >> z, alive[x][y].push_back(z);

	dx[0] = dx[1] = dx[2] = -1, dx[3] = dx[4] = 0, dx[5] = dx[6] = dx[7] = 1;
	dy[0] = dy[3] = dy[5] = -1, dy[1] = dy[6] = 0, dy[2] = dy[4] = dy[7] = 1;
	for (auto idx = 0; idx < K; ++idx)
	{
		sort_alive_tree();
		spring();
		summer();
		autumn();
		winter();
	}

	auto result = 0;
	for (int ix = 1, iy; ix <= N; ++ix)
		for (iy = 1; iy <= N; ++iy)
			if (!alive[ix][iy].empty())			result += alive[ix][iy].size();
	cout << result << endl;
	return 0;
}
// *&)*@*

봄, 여름, 가을, 겨울마다 수행되야 하는 내용을 수행하고, 반복하면 되는 시뮬레이션 문제입니다.

1. 시작시 모든 땅에는 5만큼의 양분이 깔려있다는 조건이 있습니다.
2. 봄에는 내 땅의 모든 나무에 대해서 (가장 어린 나무부터) 땅의 양분을 비교하여, 나무의 나이보다 양분이 같거나 크다면 나무의 나이는 +1, 양분은 -나무나이 입니다. 그렇지 않다면 양분은 그대로 두고, 나무의 나이도 그대로인 상태에서 죽은 나무로 분류됩니다.
3. 여름에는 2번에서 분류된 죽은 나무들 (하나의 땅에 여러개일 수 있습니다.)을 /2 해서 해당 땅에 더해줍니다. (추가 양분입니다.)
4. 가을에는 살아있는 나무들만 비교하는데, 나무의 나이가 % 5 == 0 이라면 주변 8군데에 1살 나무를 추가합니다.
5. 겨울에는 입력으로 주어졌던 Aij 만큼 땅의 양분에 더해줍니다. (추가 양분입니다.)
6. 여기까지가 1년이고, 2년 이상이라면 1번부터 반복합니다.