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

서론

시뮬레이션 문제.

풀이과정

나무를 저장하기 위해 자료형을 벡터로 가지는 2차원 배열, A의 2차원 배열, 영양분을 저장히기 위한 2차원 배열을 각각 만들어주고 문제에서 시키는대로 하면 시간초과를 고려하지 않는 구현에 큰 어려움은 없다.

주의해야할점은

처음 주어지는 나무의 위치가 (x,y)인데 r이 x이고 c가 y다.

봄에서 죽을 나무들은 다 죽인 후 여름을 진행해야한다.

가을에서 한 칸에 나이가 5의 배수인 나무가 n개 있으면 n번 번식시켜야한다.

그리고

각 칸에 나무를 저장히기 위해 벡터 컨테이너를 사용했는데, 시간초과가 떴다. 봄에서 나무가 여러개면 어린 나무부터 양분을 먹어야 하기때문에 사용한 sort, 오름차순으로 정렬된 벡터의 앞에서부터 양분을 먹고 나이를 증가시킨 후 뒤로 다시 보내기 위해 사용한 vector.erase(front)와 vector.push_back이 시간초과의 원인으로 보였다. 임시벡터를 하나 더 만들거나 우선순위 큐를 만들거나 덱을 사용하면 해결될 것으로 보였는데, 임시벡터를 만드는건 코드가 지저분해질것 같았고, sort의 시간복잡도가 nlogn이고 우선순위 큐가 logn이라서 시간복잡도를 고려하면 우선순위큐를 사용해야한다. 그런데 우선순위 큐는 가을함수를 수정해야해서 덱을 써서 vector.erase만 지워줬더니 통과했다.

구현

//c++

#pragma warning (disable:4996)

#include <deque>
#include <algorithm>
#include <cstdio>

std::deque<int> tree[11][11];
int nutriment[11][11];
int a[11][11];

int N, M, K;

void input() {
	scanf("%d %d %d", &N, &M, &K);

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

	for (int i = 0; i < M; i++) {
		int x, y, z;
		scanf("%d %d %d", &x, &y, &z);
		tree[x-1][y-1].push_back(z);
	}
}

void ss() {

	// spring
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (!tree[i][j].empty()) {
				int tmpNutriment = 0;
				std::sort(tree[i][j].begin(), tree[i][j].end());
				for (int k = 0, size = tree[i][j].size(); k < size; k++) {
					int tmp = tree[i][j].front();
					tree[i][j].pop_front();
					if (nutriment[i][j] >= tmp) {
						nutriment[i][j] -= tmp;
						tmp++;
						tree[i][j].push_back(tmp);
					}
					else {
						tmpNutriment += tmp / 2;
					}
				}
				nutriment[i][j] += tmpNutriment; // summer
			}
		}
	}
}

void fw() {
	// fall
	int dy[8] = { -1,-1,-1,0,0,1,1,1 };
	int dx[8] = { -1,0,1, -1,1, -1,0,1 };

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			for (int k = 0, size = tree[i][j].size(); k < size; k++) {
				if (tree[i][j][k] % 5 == 0) {
					for (int l = 0; l < 8; l++) {
						int ny = i + dy[l];
						int nx = j + dx[l];
						if (ny >= 0 && nx >= 0 && ny < N && nx < N) {
							tree[ny][nx].push_back(1);
						}
					}
					//break;
				}
			}
		}
	}

	// winter
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			nutriment[i][j] += a[i][j];
		}
	}

}

int main() {
	input();
	
	while (K--) {
		ss();
		fw();
	}

	int result = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			result += tree[i][j].size();
		}
	}
	printf("%d", result);
}