백준 16235번 나무 재테크 C++

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

 

처음에 입력을 받고 나무의 나이 순서대로 정렬한다.

 

봄에는 나이가 적은 순서대로 양분을 먹다가 만약 양분이 부족하면 뒤에 나무들을 전부 죽이고 죽은 나무에서 나오는 양분을 저장하는 배열에 나이/2만큼 저장한다. 이 때 배열의 뒤에서부터 죽였다. 뒤에서 죽이면 O(1)에 죽일 수 있지만 앞에서부터 죽이면 O(n)의 비용이 들기 때문이다.

 

가을에는 처음에 모든 나무들을 reverse 해서 새로 생긴 나무를 뒤에 push_back으로 놓어주고 모든 작업이 끝나면 다시 reverse 해주었다. 이렇게 하는 이유는 새로 생긴 나무는 나이가 무조건 1이기 때문에 제일 어릴 수밖에 없다. 그래서 처음에 뒤집고 새로 생긴 것을 넣어주고 다시 뒤집으면 따로 정렬을 안해줘도 되기 때문이다.

(근데 굳이 이렇게 안해도 될듯)

 

겨울에는 처음에 입력받은 양분을 더해주었다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>

using namespace std;
using ll = long long;

int n, m, k;

int dRow[8] = { -1,-1,0,1,1,1,0,-1 };
int dCol[8] = { 0,1,1,1,0,-1,-1,-1 };

vector<vector<int>> board(11, vector<int>(11, 5));
vector<vector<vector<int>>> trees(11, vector<vector<int>>(11, vector<int>()));
vector<vector<int>> deadTrees(11, vector<int>(11, 0));
vector<vector<int>> A(11, vector<int>(11));

void Sort() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			sort(trees[i][j].begin(), trees[i][j].end());
		}
	}
}

void TreeDie(int row, int col, int size) {
	for (int i = 0; i < size; i++) {
		deadTrees[row][col] += trees[row][col].back() / 2;
		trees[row][col].pop_back();
	}
}

void Spring() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			for (int k = 0; k < trees[i][j].size(); k++) {
				if (board[i][j] >= trees[i][j][k]) {
					board[i][j] -= trees[i][j][k];
					trees[i][j][k]++;
				}
				else {
					TreeDie(i, j, trees[i][j].size() - k);
					break;
				}
			}
		}
	}
}

void Summer() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			board[i][j] += deadTrees[i][j];
			deadTrees[i][j] = 0;
		}
	}
}

void Fall() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (trees[i][j].size() == 0) continue;
			reverse(trees[i][j].begin(), trees[i][j].end());
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (trees[i][j].size() == 0) continue;
			for (auto tree : trees[i][j]) {
				if (tree % 5 != 0) continue;
				for (int k = 0; k < 8; k++) {
					int nextRow = i + dRow[k];
					int nextCol = j + dCol[k];
					if (nextRow<1 || nextRow>n) continue;
					if (nextCol<1 || nextCol>n) continue;
					trees[nextRow][nextCol].push_back(1);
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (trees[i][j].size() == 0) continue;
			reverse(trees[i][j].begin(), trees[i][j].end());
		}
	}
}

void Winter() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			board[i][j] += A[i][j];
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m >> k;
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> A[i][j];
		}
	}
	for (int i = 0; i < m; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		trees[x][y].push_back(z);
	}
	Sort();
	for (int i = 0; i < k; i++) {
		Spring();
		Summer();
		Fall();
		Winter();
	}
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cnt += trees[i][j].size();
		}
	}
	cout << cnt;
};