본문 바로가기

코딩테스트 문제풀이

[백준 16235] 나무 재테크

#include <stdio.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

class Field {
private:
	vector<int> age;//size는 나무 개수
	int feed;
	int incFeed;

	int deadLine;
public:
	Field() {
		feed = 5;
	}

	void plant(int _age) {
		age.push_back(_age);
	}
	//나무를 형성하는 함수

	void setIncFeed(int _incFeed) {
		incFeed = _incFeed;
	}
	//양분 증가량 설정

	void ageSort() {
		sort(age.begin(), age.end());
	}
	//오름차순 정렬

	void feedEat() {
		deadLine = -1;
		for (int i = 0; i < age.size(); i++) {
			if (age[i] <= feed) {
				feed -= age[i];
				age[i]++;
			}
			//나이 증가
			else if(age[i] > feed) {
				deadLine = i;
				break;
			}
		}
	}
	//봄에 양분을 줌
	//나무가 몇개 뒤져야되니~
	void deadTree() {
		if (deadLine != -1) {
			int loop = age.size() - deadLine;
			for (int i = deadLine; i < age.size(); i++) {
				feed += age[i] / 2;
				age.erase(age.begin() + deadLine);
				i--;
				//cout << deadLine << "번째 제거함.";
			}
		}
	}
	//양분이 부족한 나무는 모두 죽음

	bool isExistTree() {
		if (age.size() <= 0) {
			return false;
		}
		return true;
	}
	//나무 존재를 확인

	int breedTreeNum() {
		int cnt = 0;
		for (int i = 0; i < age.size(); i++) {
			if (age[i] % 5 == 0) {
				cnt++;
			}
		}
		return cnt;
	}
	//나무 번식

	void addFeed() {
		feed = feed + incFeed;
		
	}
	//나무 양분 추가

	int getTreeNum() {
		return age.size();
	}

	void printInfo() {
		cout << "<" << feed << "," << incFeed << ">";
		cout << "{" << getTreeNum() << "}";
		//cout << "{B" << breedTreeNum() << "B}";
	
		cout << "(";
		for (int i = 0; i < age.size(); i++) {
			cout << age[i] << ",";
		}
		cout << ")";
		cout << "";
	}
	//정보 출력
};

int main(void) {
	int N; //가로 세로 크기
	int M; //나무 개수
	int K; //연도 수
	//처음 양분은 모든 칸에 5개만큼.
	
	cin >> N;
	cin >> M;
	cin >> K;

	//Field fields[11][11];
	
	Field **fields = new Field*[N];
	for (int i = 0; i < N; i++) {
		fields[i] = new Field[N];
	}
	//배열 추가

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int _incFeed;
			cin >> _incFeed;
			fields[j][i].setIncFeed(_incFeed);
		}
	}
	//양분 세팅
	
	vector<pair<int, int> > treeLoc;
	for (int i = 0; i < M; i++) {
		int x, y, z;
		cin >> x;
		cin >> y;
		cin >> z;
		x--;
		y--;
		//각각 x, y좌표, 나이

		treeLoc.push_back(pair<int, int>(y, x));
		fields[y][x].plant(z);
	}
	//나무를 심음

	//----------------------------init---------------------
	for (int year = 0; year < K; year++) {
		treeLoc.clear();
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (fields[i][j].isExistTree()) {
					treeLoc.push_back(pair<int, int>(i, j));
				}
			}
		}
		//위치정보 갱신

		//cout << year << endl;
		for (int i = 0; i < treeLoc.size(); i++) {
			fields[treeLoc[i].first][treeLoc[i].second].ageSort();
			//정렬
			fields[treeLoc[i].first][treeLoc[i].second].feedEat();
			//먹이를 줌
		}
		//봄 먹이를 줌
		
		for (int i = 0; i < treeLoc.size(); i++) {
			fields[treeLoc[i].first][treeLoc[i].second].deadTree();
			//cout << fields[treeLoc[i].second][treeLoc[i].first].getDeadLine();
			
			//나무 쥬금
			if (!fields[treeLoc[i].first][treeLoc[i].second].isExistTree()) {
				treeLoc.erase(treeLoc.begin() + i);
				i--;
			}
			//나무가 없다면 리스트에서 제거
			//cout << endl;
		}
		//여름 나무가 뒤짐

		int loop = treeLoc.size();
		for (int i = 0; i < loop; i++) {
			int breedNum = fields[treeLoc[i].first][treeLoc[i].second].breedTreeNum();
			//cout << breedNum << endl;
			//5의 배수 나이를 가진 나무의 개수
			if (breedNum > 0) {
				for (int breed = 0; breed < breedNum; breed++) {
					pair<int, int> loc[] = {	
						pair<int, int>(treeLoc[i].first - 1, treeLoc[i].second - 1),
						pair<int, int>(treeLoc[i].first - 1, treeLoc[i].second ),
						pair<int, int>(treeLoc[i].first - 1, treeLoc[i].second + 1),
						pair<int, int>(treeLoc[i].first, treeLoc[i].second - 1),
						pair<int, int>(treeLoc[i].first, treeLoc[i].second + 1),
						pair<int, int>(treeLoc[i].first + 1, treeLoc[i].second - 1),
						pair<int, int>(treeLoc[i].first + 1, treeLoc[i].second),
						pair<int, int>(treeLoc[i].first + 1, treeLoc[i].second + 1)
					};
					//주변 8칸
					for (int j = 0; j < 8; j++) {
						if (loc[j].second >= 0 && loc[j].second < N && loc[j].first >= 0 && loc[j].first < N) {
							fields[loc[j].first][loc[j].second].plant(1);
						}
					}
				}
				//그만큼 심음
			}
		}
		//가을 애 낳음

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				fields[i][j].addFeed();
			}
		}
		//겨울 양분추가

		//for (int i = 0; i < N; i++) {
		//	for (int j = 0; j < N; j++) {
		//		fields[i][j].printInfo();
		//	}
		//	cout << endl;
		//}
		//cout << endl;
		////나무 정보 확인
	}
	treeLoc.clear();
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (fields[i][j].isExistTree()) {
				treeLoc.push_back(pair<int, int>(j, i));
			}
		}
	}
	//위치정보 갱신
	int result = 0;
	for (int i = 0; i < treeLoc.size(); i++) {
		result += fields[treeLoc[i].second][treeLoc[i].first].getTreeNum();
	}
	cout << result;
	//결과 출력
	return 0;
}