[백준] 16235번 나무 재테크

16235번: 나무 재테크

쉽길래 대충 짜고 제출했다가 시간 초과로 여러 번 낭패 본 쉽지 않은 문제이다.

sort로 정렬하기 전에 죽은 나무를 제외시키는 것이 관건인 것 같다.

이차원 벡터를 이용하여 나무들을 저장해주었다.

 

봄과 여름

각 칸에 있는 모든 나무들을 검사한다.

양분을 먹을 수 있는 나무는 살 수 있으므로 큐에 나이를 넣어주고

양분을 먹지 못하는 나무는 양분이 되므로 나이/2 값을 양분 변수에 넣어준다.

 

현재 칸의 모든 나무들의 검사가 끝나면

죽은 나무를 걸러주기 위해 clear로 현재 벡터를 비워준 다음

큐에 저장해두었던 살아있는 나무들만 벡터에 다시 넣어준다.

양분 변수에 저장해두었던 값도 양분 배열에 더해준다.

 

가을과 겨울

가을은 하라는대로 하면 되고

겨울은 양분을 추가할 때마다 그 칸의 나무 벡터를 오름차순 정렬시켜줘야 한다.

 

K번만큼 이 과정을 반복하고

각 칸의 벡터 사이즈를 더해서 출력하면 된다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int N, M, K, x, y, z, cnt, food;
int arr[11][11], A[11][11], dx[8] = { -1, -1, -1, 0, 0, 1, 1, 1 }, dy[8] = { -1, 0, 1, -1, 1, -1, 0, 1 };
vector <int> tree[11][11];
queue <int> tmp;
void SpringAndSummer() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < tree[i][j].size(); k++) {
				if (tree[i][j][k] <= arr[i][j]) { //나무가 양분을 먹을 수 있다면
					arr[i][j] -= tree[i][j][k];
					tmp.push(tree[i][j][k] + 1); //나이 증가
				}
				else food += tree[i][j][k] / 2; //양분을 먹지 못해 죽은 나무는 양분이 됨
			}
			tree[i][j].clear();
			while (!tmp.empty()) tree[i][j].push_back(tmp.front()), tmp.pop(); //살아 있는 나무만 저장한다
			arr[i][j] += food, food = 0;
		}
	}
}
void FallAndWinter() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < tree[i][j].size(); k++) {
				if (tree[i][j][k] % 5 == 0) { //가을엔 나이가 5의 배수인 나무들이 번식한다
					for (int l = 0; l < 8; l++) {
						x = i + dx[l], y = j + dy[l];
						if (x >= 0 && x < N && y >= 0 && y < N) tree[x][y].push_back(1);
					}
				}
			}
		}
	}
	for (int i = 0; i < N; i++) { //겨울엔 양분 추가
		for (int j = 0; j < N; j++) {
			arr[i][j] += A[i][j];
			if (!tree[i][j].empty()) sort(tree[i][j].begin(), tree[i][j].end());
		}
	}
}
int main() {
	cin >> N >> M >> K;
	for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) cin >> A[i][j];
	for (int i = 0; i < M; i++) {
		cin >> x >> y >> z;
		tree[x - 1][y - 1].push_back(z);
	}
	fill(&arr[0][0], &arr[10][11], 5);
	for (int i = 0; i < K; i++) SpringAndSummer(), FallAndWinter();
	for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) cnt += tree[i][j].size();
	cout << cnt;
	return 0;
}