[16235번] 나무 재테크

16235번: 나무 재테크

 

www.acmicpc.net

시간제한이 0.3초로 꽤나 빡빡하다.

 

처음 접근은 3차원 벡터를 이용해서 각 위치(r,c)에 나무 정보를 저장해서 정렬을 하려고 했으나, 정렬이 반복되면 느릴꺼 같아서 정렬이 필요 없는 우선순위 큐를 사용하기로 했다.

1. 봄에 나이가 적은 순으로 양분을 흡수하기 때문에, 2차원 우선순위 큐를 이용해서 나무정보를 저장

2. 나무정보를 하나씩 뽑아서, 봄에 양분 흡수가능하면 다른 임시 우선순위 큐에 저장, 흡수가 불가능하면 죽은 나무의 나이/2를 death배열에 저장

3. 임시 우선순위 큐를 현 위치 나무정보를 가지고 있는 우선순위 큐에 복사

4. 여름에 death배열을 이용해 양분 업데이트

5. 가을에 8방 탐색을 통한 번식

6. 겨울에 양분 업데이트

이런 식으로 풀었다. 결과는 시간초과

다시 우선순위 큐 대신, 3차원 벡터를 통해서 나무정보를 저장하고 일일이 정렬을 해주는 방식으로 풀었다.

결과는 AC.

왜 이런 결과가 나왔는지 이해가 되지 않아서 여러 곳에 질문을 하고 다녔다.

"우선순위 큐를 이용한것과 벡터를 이용해 정렬을 했을 때 빅오 복잡도는 같지만 이 문제의 경우 모든 나무를 넣은 후, 보기 때문에 우선순위큐를 사용할 시 상수가 더 크기 때문이다."라는 답을 받았다.

자료구조를 공부를 다시 해보자.

#include <iostream>
#include <vector>
#include <algorithm>
#define vi vector<int>  
#define vii vector<vi>
#define viii vector<vii>
using namespace std;
int N, M, K;
int drc[] = { -1,-1,-1,0,1,1,1,0,-1,0,1,1,1,0,-1,-1 };
int energy[11][11], add[11][11], death[11][11];
vector<int> tree[11][11];
//viii tree(11, vii(11));

bool chk(int r, int c) {
	if (!(r<1 || c<1 || r>N || c>N)) return true;
	else return false;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> N >> M >> K;
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			cin >> add[r][c];
			energy[r][c] = 5;
		}
	}
	for (int i = 0; i < M; i++) {
		int r, c, a;
		cin >> r >> c >> a;
		tree[r][c].push_back(a);
	}
	while (K--) {
		//봄
		for (int r = 1; r <= N; r++) {
			for (int c = 1; c <= N; c++) {
				if (tree[r][c].size() == 0)continue;
				vector<int>tmp;
				sort(tree[r][c].begin(), tree[r][c].end());
				for(int i=0;i<tree[r][c].size();i++) {
					if (tree[r][c][i] <= energy[r][c]) {
						energy[r][c] -= tree[r][c][i];
						tmp.push_back(tree[r][c][i] + 1);
					}
					else {
						death[r][c] += (tree[r][c][i] / 2);
					}
				}
				tree[r][c].clear();
				for (int i = 0; i < tmp.size(); i++)
					tree[r][c].push_back(tmp[i]);
			}
		}

		//여름
		for (int r = 1; r <= N; r++) {
			for (int c = 1; c <= N; c++) {
				if (death[r][c] == 0)continue;
				energy[r][c] += death[r][c];
				death[r][c] = 0;
			}
		}

		//가을
		for (int r = 1; r <= N; r++) {
			for (int c = 1; c <= N; c++) {
				if (tree[r][c].size() == 0)continue;
				for(int i=0;i<tree[r][c].size();i++) {
					int top = tree[r][c][i];
					if (top % 5 != 0)continue;
					for (int d = 0; d < 8; d++) {
						int nr = r + drc[d];
						int nc = c + drc[d + 8];
						if (!chk(nr, nc))continue;
						tree[nr][nc].push_back(1);
					}
				}
			}
		}
		//겨울
		for (int r = 1; r <= N; r++) {
			for (int c = 1; c <= N; c++) {
				energy[r][c] += add[r][c];
			}
		}
	}
	int ans = 0;
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			if (tree[r][c].size() == 0)continue;
			ans += tree[r][c].size();
		}
	}
	cout << ans;
	return 0;
}