[백준 16235] 나무 재테크

문제 바로가기

16235번: 나무 재테크

 

봄, 여름, 가을, 겨울이 지나면서 수행해야하는 일이 다 다르다. 네가지 일을 모두 끝내면 한 해가 지난 것인데, 입력으로 주어진 해만큼 수행한 뒤 땅에 남아있는 나무의 수를 구하면 된다.

땅 한 칸에는 다른 문제들과는 좀 다르게 여러 나무들이 심겨져있을 수 있기 때문에 map이라는 배열의 원소로 땅의 양분(food)과 나무의 나이 vector(tree_age)를 두었다. 나무가 하나 심겨질 때마다, vector에 push_back한다.

 

봄에는 나이가 어린 나무 순으로 양분을 먹는데, 자신의 나이보다 양분이 적으면 나무는 바로 죽는다. 즉 나무의 나이보다 양분이 적은 경우가 오는 즉시(이 때의 index를 저장해둔다- k) 그 나무 나이 이상의 나무들은 다 죽는다.

따라서, 이 처리를 하기 전에 tree_age vector를 오름차순으로 정렬하고, 양분을 먹고 성장한 나무들을 새로운 vector(new_tree)에 저장한다.

 

여름에는 죽은 나무들은 양분이 되므로 k번째 나무부터 끝까지 나이/2의 양만큼 땅의 양분에 더해준다.

그리고나서 tree_age는 살아있는 나무의 나이만 담겨진 new_tree로 바꾼다.

 

가을과 겨울은 구현하기 매우 쉽다.

가을에는 나무 나이가 5의 배수인 경우 인접한 8개의 땅에 나이가 1인 나무가 새로 생겨나므로, 인접한 8개의 위치의 tree_age에 1을 push_back 한다.

 

겨울에는 입력으로 주어진 양분의 양만큼 현재 땅의 양분에 더해준다.

이를 K만큼 반복하면 된다.

 

처음에 이 문제에서,

"각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 떨어진 칸의 개수, c는 가장 왼쪽으로부터 떨어진 칸의 개수이다. r과 c는 1부터 시작한다."

라고 주어지는데, 뒤에 입력에서는 

"처음 두 개의 정수는 나무의 위치 (x, y)를 의미하고,"

라고 나온다.

 

(x, y)만 보고 당연히 가로 세로라고 생각하고 풀었는데 윗 부분에서 r이 세로, c가 가로임을 명시해두었기 때문에

x가 세로, y가 가로 값으로 생각하고 풀어야했다. 

 

이런 자잘한 실수,, out...

문제 자체는 별로 안 어려웠다 ~!

 

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

struct info
{
	int food;
	vector<int> tree_age;
};

int N, M, K;
info map[11][11];
int new_food[11][11];
int pos[8][2] = { {-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1} };

bool isIn(int x, int y)
{
	if (x > 0 && x <= N && y > 0 && y <= N)
	{
		return true;
	}
	return false;
}

void spend_year()
{
	
	
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{

			vector<int> new_tree;

			sort(map[i][j].tree_age.begin(), map[i][j].tree_age.end());
			
			//봄
			int t;
			for (t = 0; t < map[i][j].tree_age.size(); t++)
			{
				if (map[i][j].food - map[i][j].tree_age[t] < 0)
				{
					break;
				}
				else
				{
					map[i][j].food -= map[i][j].tree_age[t];
					new_tree.push_back(map[i][j].tree_age[t] + 1);
				}

			}

			//여름
			for (int k = t; k < map[i][j].tree_age.size(); k++)//죽은나무들 양분으로
			{
				map[i][j].food += map[i][j].tree_age[k] / 2;
			}

			map[i][j].tree_age.clear();
			map[i][j].tree_age = new_tree;

		}
	}

	
	//가을
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			for (int t = 0; t < map[i][j].tree_age.size(); t++)
			{
				if (map[i][j].tree_age[t] % 5 == 0)
				{
					for (int k = 0; k < 8; k++)
					{
						int ny = i + pos[k][0];
						int nx = j + pos[k][1];

						if (isIn(nx, ny))
						{
							map[ny][nx].tree_age.push_back(1);
						}
					}
				}
			}


		}
	}

	//겨울
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			map[i][j].food += new_food[i][j];
		}
	}
}

int main()
{
	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			cin >> new_food[i][j];
		}
	}

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			map[i][j].food = 5;
		}
	}

	for (int i = 0; i < M; i++)
	{
		int x, y, age;
		cin >> y >> x >> age;
		map[y][x].tree_age.push_back(age);
	}

	for (int i = 0; i < K; i++)
	{
		spend_year();
	}

	int cnt = 0;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			cnt += map[i][j].tree_age.size();
		}
	}

	cout << cnt << endl;
	return 0;
}