백준 16235번: 나무 재테크

문제

문제 바로가기> 백준 16235번: 나무 재테크

풀이

처음에 priority_queue와 queue를 이용해서 구현했더니, 시간 초과가 발생했다. priority_queue에 넣고 빼는 데 시간이 꽤 걸리는 듯했다. 처음에 입력으로 주어지는 나무의 위치가 모두 다르기 때문에 deque를 사용하여 새로 생기는 나무만 앞에 넣어주면 정렬할 필요가 없기 때문에 아래와 같이 풀었다!

#include<iostream>
#include<deque>
#define MAX 11
using namespace std;

int N, M, K;
deque<int> tree[MAX][MAX];
int nutrient[MAX][MAX], A[MAX][MAX];
int dy[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int dx[] = { -1, 0, 1, -1, 1, -1, 0, 1 };

void input() {
	cin >> N >> M >> K;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			nutrient[i][j] = 5;
			cin >> A[i][j];
		}
	}
	int y, x, age;
	for (int i = 0; i < M; i++) {
		cin >> y >> x >> age;
		tree[y-1][x-1].push_back(age);
	}
}

void spring_and_summer() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int t;
			// 봄 - 양분을 먹을 수 있는 경우, 양분을 먹고 나이  1 증가
			for (t = 0; t < tree[i][j].size(); t++) {
				if (nutrient[i][j] < tree[i][j][t]) break; //양분을 먹지 못하고 즉시 죽음
				nutrient[i][j] -= tree[i][j][t];
				tree[i][j][t]++;
			}

			// 여름 - 봄에 죽은 나무들이 양분으로 변함 
			for (int k = tree[i][j].size() - 1; k >= t; k--) {
				nutrient[i][j] += tree[i][j][k] / 2;
				tree[i][j].pop_back();
			}
		}
	}
}

void fall() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			for (int t = 0; t < tree[i][j].size(); t++) {
				if (tree[i][j][t] % 5) continue;  // 나무 나이가 5의 배수가 아닌 경우 
				for (int d = 0; d < 8; d++) {
					int ny = i + dy[d];
					int nx = j + dx[d];
					if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
					tree[ny][nx].push_front(1); // 정렬하지 않기 위해!
				}
			}
		}
	}
}

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

void output() {
	int ans = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) ans += tree[i][j].size();
	}
	cout << ans;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	input();
	while (K--) {
		spring_and_summer();
		fall();
		winter();
	}
	output();
}