백준 16235번: 나무 재테크 (C++)

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

16235번: 나무 재테크

 

특별한 알고리즘이랄 것이 없지만, 벡터를 활용하는 약간의 센스가 필요하다.

 

정수를 담는 벡터 자료형을 이차원 배열로 선언한다.

 

그래야 이차원 좌표상의 한 공간에 나무가 여러개 쌓이는 효과를 볼 수 있다.

 

그리고, 여름에 나무의 삭제가 발생할 때, 삭제되는 나무에 대한 처리를 할 때, vector.erase를 사용하고, 삭제되는 나무들에 대한 정보를 큐로 옮긴 이후에, 큐에서 pop하면서 처리를 해서 시간초과를 받았다.

 

이를 해결하기위해서, 봄에 땅으로부터 영양분을 흡수하는 것은 어짜피 나무가 나이로 정렬된 상태로 이루어지고, 특정 나이가 땅의 양분보다 많은 순간이 온다면, 그 나무보다 나이가 많은 나무들은 자연스럽게 확인할 가치가 없어지기 때문에, 봄에 영양분을 흡수했던 나무들을 임시 벡터에 넣어두고, 실패지점 이후에 원본 벡터를 clear한 이후에, 임시 벡터에 들어있는 데이터를 원래 벡터에 옮겨주면 여름에 대한 구현을 할 수 있다.

 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
ll grd[11][11];
int igr[11][11], n, m, k;
vector<ll> v[11][11];
int dr[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dc[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
int main(void) {
	//1-indexed
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> igr[i][j];
			grd[i][j] = 5;
		}
	}
	for (int i = 1; i <= m; i++) {
		int r, c, age;
		cin >> r >> c >> age;
		v[r][c].push_back(age);
	}
	for (int i = 1; i <= k; i++) {
		//봄
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (v[i][j].size() > 0) { //i행 j열에 나무가 존재하면
					vector<ll> tmp;
					sort(v[i][j].begin(), v[i][j].end()); //어린 나무부터
					//땅양분이 나이보다 많으면 나이 증가, 땅 양분 감소
					ll dead = 0;
					for (int t = 0; t < v[i][j].size(); t++) {
						if (v[i][j][t] <= grd[i][j]) {
							tmp.push_back(v[i][j][t] + 1);
							grd[i][j] -= v[i][j][t];
						}
						else {
							dead += v[i][j][t] / 2;
						}
					}
					//여름
					v[i][j].clear();
					v[i][j] = tmp;
					grd[i][j] += dead;
				}
			}
		}

		//가을
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (v[i][j].size() > 0) {
					for (int t = 0; t < v[i][j].size(); t++) {
						if (v[i][j][t] % 5 == 0) {
							for (int ii = 0; ii < 8; ii++) {
								int nr = i + dr[ii];
								int nc = j + dc[ii];
								if (nr < 1 || nc < 1 || nr > n || nc > n) continue;
								v[nr][nc].push_back(1);
							}
						}
					}
				}
			}
		}

		//겨울
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				grd[i][j] += igr[i][j];
			}
		}
	}
	ll cnt = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (v[i][j].size() > 0) cnt += v[i][j].size();
		}
	}
	cout << cnt;
	return 0;
}