백준 16235 [C++]

www.acmicpc.net/problem/16235

16235번: 나무 재테크

1. 풀이방법

- 단순한 구현 문제입니다.

 

- 문제는 간단하고 이해도 어렵지 않지만, 시간제한이 0.3초 인 점을 감안하여야 합니다.

 

- 문제에서의 단계대로 차례차례 진행해줍니다.

 

 

2. 주의사항

- 전 처음에 시간제한 및 어린나이부터 진행되어야 한다는 문제를 보고 우선순위 큐를 생각해서 접근하였는데,

 

- 정답은 잘 뽑아내는 것 같으나, 시간초과가 계속 되어 결국 자료형을 vector로 바꿔서 봄에만 정렬을 하여 사용하였습니다.

 

- vector를 사용하자니, 죽은 나무를 뽑아내는 것이 문제였는데, vector는 index로 쉽게 접근이 가능하나 원하는 위치의데이터를 맘대로 뽑기는 어렵습니다.

 

- 그래서 양분이 부족해지는 지점이 딱 왔을 때, 그 이차원벡터배열의 맨뒤부터 양분/2를 더해주면서 pop_back() 해주었습니다.

 

 

3. 나의코드

#include<bits/stdc++.h>
using namespace std;

int n, m, K;
int ground[11][11]; // 양분의 양
vector<int> treeageset[11][11]; //나이 기준 정렬
int s2d2[11][11];
int dx[8] = { -1,-1,-1,0,0,1,1,1 };
int dy[8] = { -1,0,1,-1,1,-1,0,1 };
int tmpv[1001];
int presize[11][11]; 

void inputs() {
	cin >> n >> m >> K;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			ground[i][j] = 5;
			cin >> s2d2[i][j];
		}
	}
	int x, y, z;
	for (int i = 0; i < m; i++) {
		cin >> x >> y >> z;
		treeageset[x][y].push_back(z);
	}
}
bool boundcheck(int x, int y) {
	return (x >= 1 && x <= n && y >= 1 && y <= n);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	for (int i = 0; i < K; i++) { //1년

		//봄
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k <= n; k++) {
				if (treeageset[j][k].empty()) continue;
				int tmpground = ground[j][k];
				ground[j][k] = 0;
				sort(treeageset[j][k].begin(), treeageset[j][k].end());
				int vsize = treeageset[j][k].size();
				for (int a = 0; a < vsize; a++) {
					if (tmpground >= treeageset[j][k][a]) {
						tmpground -= treeageset[j][k][a];
						treeageset[j][k][a]++;
					}
					else {
						for (int b = vsize - 1; b >= a; b--) {
							ground[j][k] += treeageset[j][k][b] / 2;
							treeageset[j][k].pop_back();
						}
						break;
					}
				}
				ground[j][k] += tmpground; //남은 양분+죽은나무의 양분
			}
		}


	//새로 추가되는 나무들은 번식시키지 않기 위해서
	for (int j = 1; j <= n; j++) { 
		for (int k = 1; k <= n; k++) {
			presize[j][k] = treeageset[j][k].size();
		}
	}
	//가을 번식
	for (int j = 1; j <= n; j++) {
		for (int k = 1; k <= n; k++) {
			for (int a = 0; a < presize[j][k]; a++) {
				if (treeageset[j][k][a] % 5 == 0) {
					for (int b = 0; b < 8; b++) {
						int nextx = j + dx[b];
						int nexty = k + dy[b];
						if (boundcheck(nextx, nexty)) {
							treeageset[nextx][nexty].push_back(1);
						}
					}
				}
			}
			ground[j][k] += s2d2[j][k]; //양분 보급
		}
	}
}
	int resultsum = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			resultsum += treeageset[i][j].size();
		}
	}
	cout << resultsum;
	return 0;
}