백준 - 16235번 : 나무 재테크 (C++)

풀이 방법 : 단순 구현

문제가 길어서 헷갈리는 것만 빼면 어려울게 없는 문제, 착실히 요구사항을 따라가자.

양분은 어린나무부터 먹는다. 정렬을 해도 좋은 선택이겠지만 어차피 나중에 번식으로 인하여 추가되는 나무는 무조건 이전 나무보다 어린 나무일 것이므로 vector를 역순으로 반복문을 돌려주면 될 것이라고 생각해 굳이 정렬을 하지 않았다.

같은 이유로 역순으로 반복문을 돌리면 양분이 부족한 경우가 생길 경우 그 다음 나무 또한 무조건 양분이 부족한 경우다. 따라서 양분이 부족한 경우가 생긴 경우 해당 Index를 저장하고 0부터 해당 Index까지의 나무들의 나이 / 2 를 현재 양분에 더해주고 그 범위의 나무들을 삭제 처리해주었다.

이렇게 처리를 해주다가 양분을 제대로 먹고 나이를 먹은 나무들에 한해서 그 나이가 5로 나누어떨어지는 경우 번식을하여 나무가 추가될 숫자를 증가시켜주었다.
이후 반복문을 돌려가며 8방향에 해당하는 땅에 나이가 1인 나무를 추가해주었다.

마지막으로 각 땅에 입력받은 양분들을 추가 처리해준다.
이를 K번 반복해주면 된다.

#include <iostream>
#include <vector>

using namespace std;

int N, M, K;
int A[11][11] = {}; //매년 추가될 양분 저장
int CurrentA[11][11] = {}; //현재 양분 저장
int NewWoodCnt[11][11] = {}; //새롭게 추가될 나무 갯수
vector<int> Age[11][11] = {}; // 현재 살아있는 나무 저장
int CurrentWoodCnt = 0; //현재 살아있는 나무 갯수 저장

int DirX[8] = { 0,0,-1,-1,-1,1,1,1 };
int DirY[8] = { 1, -1, 1,0,-1, 1,0,-1 };

void WoodGrow(int CurrentYear)
{
	if (CurrentYear == K)
		return;

	for (int i = 1; i <= N; ++i)
	{
		for (int j = 1; j <= N; ++j)
		{
			int Size = Age[i][j].size();

			if (Size == 0)
				continue;

			int Index = -1;

			for (int k = Size - 1; k >= 0; --k)
			{
				if (CurrentA[i][j] < Age[i][j][k])
				{
					Index = k;
					break;
				}

				else
				{
					CurrentA[i][j] -= Age[i][j][k];
					Age[i][j][k] += 1;

					if (Age[i][j][k] % 5 == 0)
					{
						++NewWoodCnt[i][j];
					}

				}
			}

			for (int k = 0; k <= Index; ++k)
			{
				CurrentA[i][j] += Age[i][j][k] / 2;
			}

			if (Index == -1)
				continue;

			auto iter = Age[i][j].begin();
			Age[i][j].erase(iter, (iter + Index + 1));

			CurrentWoodCnt -= (Index + 1);
		}
	}

	for (int i = 1; i <= N; ++i)
	{
		for (int j = 1; j <= N; ++j)
		{
			CurrentA[i][j] += A[i][j];

			if (NewWoodCnt[i][j] == 0)
				continue;

			for (int k = 0; k < 8; ++k)
			{
				int NewY = i + DirY[k];
				int NewX = j + DirX[k];

				if (NewY < 1 || NewY > N ||
					NewX < 1 || NewX > N)
					continue;

				for (int cnt = 0; cnt < NewWoodCnt[i][j]; ++cnt)
				{
					Age[NewY][NewX].push_back(1);
					++CurrentWoodCnt;
				}

			}

			NewWoodCnt[i][j] = 0;
		}
	}

	WoodGrow(CurrentYear + 1);
}

int main()
{
	cin >> N >> M >> K;
	CurrentWoodCnt = M;

	for (int i = 1; i <= N; ++i)
	{
		for (int j = 1; j <= N; ++j)
		{
			cin >> A[i][j];
			CurrentA[i][j] = 5;
		}
	}

	for (int i = 0; i < M; ++i)
	{
		int x, y, age;
		cin >> x >> y >> age;

		//입력으로 주어지는 나무의 위치는 서로 다름
		Age[x][y].push_back(age);
	}

	WoodGrow(0);
	
	cout << CurrentWoodCnt;
}

구현 자체는 빠르게 끝냈는데 입력 받은 초기의 나무의 좌표의 x, y를 반대로 생각해서 시간 낭비했다. 좌표를 다룰 때는 문제가 요구하는 입력 순서대로 생각하자...