[BeakJoon 16235] 나무 재테크

안녕하세요. 이번 포스팅에서는 백준 16235번 나무 재테크 문제를 풀어보겠습니다.

 

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

16235번: 나무 재테크

 

해당 문제는 위 링크에서 확인하실 수 있습니다.

 

우선 이 문제를 풀기 위해 별도의 알고리즘을 많이 고민하실 필요는 없습니다.

 

 

 

해당 문제를 시뮬레이션으로 구현하시면 되는데, 문제는 이 문제의 제한이 빡빡합니다. 시간제한이 0.3초라서, 매번 sort를 하기 어렵습니다.

 

sort를 하는 이유는 어린 나무부터 양분을 먹기 위해서입니다.

 

따라서 효율적으로 양분을 먹이고, 죽은 나무에 대한 처리과정을 진행해주셔야 합니다.

 

저 같은 경우는 

 

봄&여름 : 현재 나무들이 저장된 벡터를 순회하며, 죽지 않는 나무는 newV에 넣고, 죽은 나무는 death라는 vector에 넣었습니다. 

 

죽지 않은 나무의 경우 양분을 나이만큼 빼 주었고, 나이를 1 증가시켜주었습니다.

죽은 나무의 경우 나이/2를 더해 주었습니다.

 

가을&겨울 : 가을의 경우 추가하려는 나무의 인덱스가 넘어가는 지 확인(1)을 한 뒤, 추가할 수 있으면 벡터의 앞부분에 넣어주었습니다. 추가되는 나무는 나이가 1로 고정이기 때문에 추가적인 sort를 하지 않고자 앞부분에 넣었습니다.

 

또한 벡터의 앞부분에 넣는 연산을 v.insert(v.begin(), a)로 수행할 수 있는데, 해당 문법을 사용하시면 시간이 오래 걸립니다. 

 

따라서 tmp배열을 하나 만들어서 새로 추가되는 나무들을 저장한 뒤, vector의 원소는 이미 정렬되어 있으므로 tmp배열 뒤에 추가만 해주었습니다.

 

<소스 코드>

#include <bits/stdc++.h>
using namespace std;

int n, m, k, board[14][14], A[14][14];
const int dir[8][2] = {{-1,-1}, {-1,0}, {-1,1}, {0,-1}, {0, 1}, {1, -1}, {1, 0}, {1,1}};
typedef struct tree{
	int y,x,z;
}TREE;
vector<TREE> v;
bool cmp(TREE a, TREE b) {
	if(a.z != b.z) return a.z <= b.z;
	return 0;
}
void springAndSummer() {
	vector<TREE> death;
	vector<TREE> newV;
	for(int i = 0; i < v.size(); i++) {
		int y=v[i].y, x=v[i].x, age=v[i].z;
		if(board[y][x] >= age) {
			board[y][x]-=age;
			v[i].z++;
			newV.push_back(v[i]);				
		} else death.push_back(v[i]);	
	}
	for(int i = 0; i < death.size(); i++) board[death[i].y][death[i].x]+=(death[i].z/2);
	v=newV;
}
void autumnAndWinter() {
	vector<TREE> tmp;
	for(int i = 0; i < v.size(); i++) {
		int y=v[i].y, x=v[i].x, age=v[i].z;
		if(age%5==0) {
			for(int d = 0; d < 8; d++) {
				int ny = y+dir[d][0], nx = x+dir[d][1];
				if(ny < 1 || nx < 1 || ny > n || nx > n) continue;
				tmp.push_back({ny,nx,1});
			}
		}
	}
	
	for(auto a : v) tmp.push_back(a);
	v = tmp;
	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 a, b, c; cin >> a >> b >> c;
		v.push_back({a, b, c});
	}
	fill(&board[0][0], &board[0][0]+14*14, 5);
	sort(v.begin(), v.end(), cmp);
	
	while(k--) { 
		springAndSummer();
		autumnAndWinter(); 
	}
	
	cout << v.size() << '\n';
	return 0;
}

 

*저의 글에 대한 피드백이나 지적은 언제나 환영합니다.