BOJ : 16235 나무 재테크

---

[BOJ 16235(G4) 리뷰] 

2021년에 푸는 첫 문제이다..!

문제를 보면 알겠지만 조건에 대한 설명이 아주 친절하게 나와 있다. 그렇기에 문제에서 주어진대로만 구현을 하면 될것같았다. 각 계절마다 함수를 만들어 벡터와 배열을 이용하여 구현하고, 테스트케이스도 다 맞길래 기분좋게 제출을 했다.

하지만 역시.. 이렇게 쉽게 풀릴 문제는 아니였다. 제출하자마자 시간초과가 떴다.

시간초과의 원인이 뭔지 분석을 해봤다.
일단 첫번째 문제로는 봄에 죽은 나무들을 별도의 벡터에 저장을하고, 여름 함수를 만들어서 여름함수에 양분을 추가하는 작업을 했는데 이 작업이 매우 비효율적으로 보였다.

두번째는 나이가 어린 나무부터 양분을 먹기위한 조건을 만족하기 위해 1년이 지날때마다 현재의 나무들을 오름차순으로 정렬했는데, K의 최대값이 1000이므로 어쩌면 1000번의 정렬을 수행해야 한다는 점이였다.

어떻게 해결할까 고민을 많이 했는데 답이 잘 떠오르지 않아 다른 분의 풀이를 살짝 참고했다.

나는 벡터 하나에 (X좌표,Y좌표,나이)를 저장했는데, 이렇게 저장하면 동일한 좌표에 여러개의 나무가 존재할 경우 벡터의 크기가 매우 커지게 된다.

이 문제를 2차원 벡터를 통해 해결했다. 'vector <int> live[x][y]' 로 선언하여 live[x][y][k]는 x,y좌표의 k번째 나무의 나이가 될것이다. 이렇게 나무의 정보를 저장하면 봄과 여름의 작업을 한번에 수행할 수 있다. 이 부분에서 크게 시간 절약이 가능하다. 

또한 정렬 역시 N의 최대값이 10이므로 최대 100번의 정렬만 수행하면 된다.

좀 어려웠지만 그래도 배운게 많은 문제였던 것 같다.

/*
	21.01.01
	BOJ : 16236 나무 재테크 (https://www.acmicpc.net/problem/16235)
	구현, 시뮬레이션
*/

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

int N,M,K;
int A[11][11] = { 0 };
int Farm[11][11] = { 0 };
vector <int> live[11][11];

int dx[8] = { -1,-1,-1,0,0,1,1,1 };
int dy[8] = { -1, 0, 1,-1,1,-1,0,1 };

bool cmp(int a, int b)
{
	return a < b;
}

void springsummer() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (live[i][j].size() == 0) continue;

			sort(live[i][j].begin(), live[i][j].end(),cmp);

			int size = live[i][j].size();
			int sum = 0;
			vector <int> live_tree;
			for (int k = 0; k < size; k++) {
				if (Farm[i][j] >= live[i][j][k]) { //양분 섭취
					Farm[i][j] -= live[i][j][k];
					live_tree.push_back(live[i][j][k] + 1);
				}
				else {
					sum += (live[i][j][k] / 2);
				}
			}

			live[i][j].clear();
			for (int k = 0; k < live_tree.size(); k++) {
				live[i][j].push_back(live_tree[k]);
			}
			Farm[i][j] += sum;
		}
	}
}

void fall() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			int size = live[i][j].size();
			if (size == 0) continue;

			for (int k = 0; k < size; k++) {
				if (live[i][j][k] % 5 == 0) {
					for (int dir = 0; dir < 8; dir++) {
						int nx = i + dx[dir];
						int ny = j + dy[dir];
						if (nx <1 || ny< 1 || nx>N || ny>N) continue;
						live[nx][ny].push_back(1);
					}
				}
			}
			
		}
	}
}

void winter() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			Farm[i][j] += A[i][j];
		}
	}
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);
	
	cin >> N >> M >> K;
	
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> A[i][j];
			Farm[i][j] = 5;
		}
	}

	for (int i = 0; i < M; i++) {
		int x, y, age;
		cin >> x >> y >> age;
		live[x][y].push_back(age);
	}

	while (K--) {
		springsummer();
		fall();
		winter();
	}

	int ans = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			ans += live[i][j].size();
		}
	}

	cout << ans;

}