[백준 16235] 나무 재테크

문제 출처: https://www.acmicpc.net/problem/16235

풀이

나무의 위치와 나무의 나이, 특정 좌표의 나무의 갯수를 2차원벡터로 표현할 수 있으면 나머지는 구현문제입니다.

나무의 갯수: v.[i][j].size()

나무의 나이: v[i][j][k]

나무의 위치: i,j 

그리고 문제를 읽으실 때 주의하셔야 할게, 

입력받는 배열과 양분이 5로 채워져있는 배열은 문제만 보면 어떤차이인지 의미가 모호할 수 있으므로 양분증감량을 계산할 때 주의하셔야합니다.

**이 풀이는 180ms가 나오는데 풀이법에 따라 100ms,50ms, 심지어 0ms가 나오는 방법들도 있기 때문에 그런 코드들을 참고하는것도 좋을 것 같습니다.

코드

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int  yb[10][10], a[10][10];
int dy[8] = {-1,0,1,-1,1,-1,0,1 };
int dx[8] = {-1,-1,-1,0,0,1,1,1 };
int n, m, k;
//해당위치의 나무의 나이를 저장하기위해서 벡터
vector<int>v[10][10];
int main()
{
	cin.tie(0);
	cin.sync_with_stdio(false);
	cin >> n >> m >> k;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> a[i][j];
			yb[i][j] = 5;
		}
	}
	for (int i = 0; i < m; i++)
	{
		int y, x, z;
		cin >> y >> x >> z;
		v[y - 1][x - 1].push_back(z);
	}
	for (int i = 0; i < k; i++)
	{
		for (int y = 0; y < n; y++)
		{
			for (int x = 0; x < n; x++)
			{
				//봄 여름
				//나무가 있을 떄만
				if (v[y][x].size())
				{
					int dead_tree = 0;
					vector<int>temp;
					sort(v[y][x].begin(), v[y][x].end());
					for (int num = 0; num < v[y][x].size(); num++)
					{
						int age = v[y][x][num];
						//양분이 나이보다 작으면 탈출
						if (yb[y][x] >= age)
						{
							yb[y][x] = yb[y][x] - age;
							temp.push_back(age + 1);
						}
						//탈출하되 여름에 죽은게 양분으로 변하므로
						else
						{
							dead_tree = dead_tree+age / 2;
						}
					}
					//비우고 새롭게 나이먹은 나무들을 다시 담음
					v[y][x].clear();
					for (int num = 0; num < temp.size(); num++)
						v[y][x].push_back(temp[num]);
					
					yb[y][x] += dead_tree;
				}
			}
		}
		for (int y = 0; y < n; y++)
		{
			for (int x = 0; x < n; x++)
			{
				//나무가 있는 좌표에대해서만
				if (v[y][x].size())
				{
					for (int i = 0; i < v[y][x].size(); i++)
					{
						int age = v[y][x][i];
						if (age % 5 == 0)
						{
							for (int dis = 0; dis < 8; dis++)
							{
								int ny = y + dy[dis];
								int nx = x + dx[dis];
								if (nx >= 0 && ny >= 0 && nx < n && ny < n)
								{
									//인접한 칸에 나이1인 나무 생김
									v[ny][nx].push_back(1);
								}
							}
						}
					}
				}
			}
		}
		for (int y = 0; y < n; y++)
		{
			for (int x = 0; x < n; x++)
			{
				yb[y][x] += a[y][x];
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			ans += v[i][j].size();
		}
	}
	cout << ans << '\n';
}

결과