[백준][16235번] 나무 재테크

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

16235번: 나무 재테크

 

풀이과정

1. 주어진 시퀀스대로 진행되는 시뮬레이션 문제였다.

 

2. 

봄에는 현재 나무의 나이만큼 양분을 먹어 나이가 증가하거나, 양분을 못먹어 죽는 2가지 경우가 있다.

양분은 나이가 적은 순부터 우선순위를 가짐, 따라서 나이순으로 sort를 했다. 

info는 구역에 존재하는 나무의 정보이다. 해쉬 테이블처럼 사용하기 위해 vector 배열을 만들었다. vector 배열을 쓴 이이유는 같은 구역에 여러 나무가 존재 할 수 있기 때문이다.

 

여름에는 죽은 나무가 양분이 된다.

가을에는 나이가 5의 배수인 나무가 번식을 진행한다.

겨울에는 S2D2로봇이 구역마다 양분을 뿌려준다.

 

* 시간적으로는 빠른 풀이는 아닌것 같다.

 

소스코드

#include<stdio.h>
#include<vector>
#include<algorithm>
enum STATE { ALIVE, DEAD };
using namespace std;
int N, M, K;
struct tree {
	int age;
	int state;
}typedef tree;
vector<tree> info[10][10];
int s2d2[10][10];
int map[10][10];
int dx[8] = { -1, 0, 1, -1, 1, -1, 0, 1 };
int dy[8] = { -1, -1, -1, 0, 0, 1, 1, 1 };
bool desc(const tree &t1, const tree &t2) {
	if (t1.age < t2.age) {
		return true;
	}
	else {
		return false;
	}
}

void spring() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (info[i][j].size() == 0) continue;
			if (info[i][j].size() > 1) {
				sort(info[i][j].begin(), info[i][j].end(), desc);
			}
			for (int k = 0; k < info[i][j].size(); k++) {
				if (info[i][j][k].age <= map[i][j]) {
					map[i][j] -= info[i][j][k].age;
					info[i][j][k].age++;
				}
				else {
					info[i][j][k].state = DEAD;
				}
			}
		}
	}
}

void summer() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (info[i][j].empty()) continue;
			vector<tree>::iterator itr = info[i][j].begin();
			for (itr; itr != info[i][j].end();) {
				if (itr->state == DEAD) {
					map[i][j] += (itr->age / 2);
					itr = info[i][j].erase(itr);
				}
				else {
					itr++;
				}
			}
		}
	}
}

void fall() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (info[i][j].empty()) continue;
			for (int k = 0; k < info[i][j].size(); k++) {
				if (info[i][j][k].age % 5 == 0) {
					for (int l = 0; l < 8; l++) {
						int nx = j + dx[l];
						int ny = i + dy[l];
						if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
						tree tmp = { 1, ALIVE };
						info[ny][nx].push_back(tmp);
					}
				}
			}
		}
	}
}

void winter() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			map[i][j] += s2d2[i][j];
		}
	}
}

int solution() {
	for (int i = 0; i < K; i++) {
		//spring -> 양분을 먹고 나이 증가 (적은 나이 부터 먹는다)
		spring();
		//summer -> 봄에 죽은 나무가 양분으로 변한다. 나이/2
		summer();
		//fall -> 나무 번식 나이가 5의 배수이면 인접 8칸
		fall();
		//winter 양분 추가
		winter();
	}

	int answer = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (info[i][j].size() == 0) continue;
			answer += info[i][j].size();
		}
	}
	return answer;
}

int main()
{
	scanf("%d %d %d", &N, &M, &K);

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int n;
			scanf("%d", &n);
			map[i][j] = 5;
			s2d2[i][j] = n;
		}
	}

	for (int i = 0; i < M; i++) {
		int x, y, age;
		scanf("%d %d %d", &y, &x, &age);
		tree tmp = { age, ALIVE };
		info[y - 1][x - 1].push_back(tmp);
	}
	printf("%d\n", solution());
}

결과