#16235. 나무 재테크

Problem

• 문제링크

Solution

• 시뮬레이션 문제이다.
• 봄, 여름, 가을, 겨울에 맞게 작업을 수행하면 된다.
• 단 한 칸에 여러 개의 나무가 존재할 수 있다는 점에 주목하자.

처음에 3차원 벡터로 해당 칸에 나무 정보를 저장하였지만 계절마다 작업을 수행할 때 상당히 비효율적이라 시간초과가 떴다.

→ 문제의 조건을 잘 보면 답이 보인다. (항상 느끼는 거지만 어떤 자료구조를 선택할지가 중요)

1. 나이가 어린 나무부터 양분을 먹는다. (해당 칸에 있는 나무 정보를 순회할 때 어린 나무부터 접근해야 한다.)
2. 나무 정보를 처음에 입력받을 때 한 칸에 하나씩만 받는다.
3. 나무가 추가될 때 나이가 1인 나무가 추가된다.
4. 나이가 클수록 먼저 죽음(나이만큼 양분을 먹기 때문이다.)

위 조건을 도합하면 deque 가 가장 적합하다. deque<int> tree[10][10]
나이가 어린 나무가 앞에 즉, 오름차순으로 정렬되어 있어야 하는데, 처음에 각 칸에 하나씩 입력 받고 추가될 때 앞부분에 나무를 추가해주면 되기 때문이다. 죽는건 앞에서부터 탐색을 하다가 죽는 나무가 생기면 그 뒤부터 이미 죽은 나무가 되기에 죽을 나무 개수만 카운트하고 뒤에서부터 개수만큼 pop하면 되기 때문이다.

1 Try

• code

  #include <iostream>
  #include <algorithm>
  #include <vector>
  using namespace std;
  int N, M, K, ans, diff;
  int land[10][10];
  int A[10][10];
  int dx[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };
  int dy[8] = { 0, -1, -1, -1, 0, 1, 1, 1 };
  vector<vector<vector<int>>> v;
  void Input() {
  	cin >> N >> M >> K;
  	for (int i = 0; i < N; ++i) {
  		v.resize(N);
  		for (int j = 0; j < N; ++j) {
  			v[i].resize(N);
  			cin >> A[i][j];
  			land[i][j] = 5;
  		}
  	}
  	for (int i = 0; i < M; ++i) {
  		int r, c, age;
  		cin >> r >> c >> age;
  		v[r-1][c-1].push_back(age);
  	}
  }
  void Task() {
  	// 봄, 여름
  	for (int i = 0; i < N; ++i) {
  		for (int j = 0; j < N; ++j) {
  			if (v[i][j].size() > 1) sort(v[i][j].begin(), v[i][j].end());
  			int sum = 0;
  			for (int k = 0; k < v[i][j].size(); ++k) {
  				if (v[i][j][k] == 0) continue;
  				if (land[i][j] - v[i][j][k] < 0) {
  					sum += v[i][j][k] / 2;
  					v[i][j][k] = 0; // 죽은 표시
  					diff++;
  				}
  				else {
  					land[i][j] -= v[i][j][k];
  					v[i][j][k]++;
  				}
  			}
  			land[i][j] += sum;
  		}
  	}
  	// 가을, 겨울
  	for (int i = 0; i < N; ++i) {
  		for (int j = 0; j < N; ++j) {
  			for (int k = 0; k < v[i][j].size(); ++k) {
  				if (v[i][j][k] == 0) continue;
  				if (v[i][j][k] % 5 == 0) {
  					for (int dir = 0; dir < 8; ++dir) {
  						int r = i + dx[dir];
  						int c = j + dy[dir];
  						if (r <= -1 || c <= -1 || r >= N || c >= N) continue;
  						v[r][c].push_back(1);
  					}
  				}
  			}
  			land[i][j] += A[i][j];
  		}
  	}
  }
  int main() {
  	Input();
  	while (K--) {
  		Task();
  	}
  	for (int i = 0; i < N; ++i) {
  		for (int j = 0; j < N; ++j) {
  			ans += v[i][j].size();
  		}
  	}
  	ans -= diff;
  	cout << ans << "\n";
  	return 0;
  }

  시간초과

2 Try

#include <iostream>
#include <deque>
using namespace std;
int N, M, K, ans;
int land[10][10];
int A[10][10];
int dx[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dy[8] = { 0, -1, -1, -1, 0, 1, 1, 1 };
deque<int> tree[10][10];
void Input() {
	cin >> N >> M >> K;
	ans = M;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			cin >> A[i][j];
			land[i][j] = 5;
		}
	}	
	for (int i = 0; i < M; ++i) {
		int r, c, age;
		cin >> r >> c >> age;
		tree[r - 1][c - 1].push_back(age);
	}
}
void Task() {
	// 봄, 여름
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (tree[i][j].empty()) continue;
			int sum = 0, dead_num = 0;
			for (auto iter = tree[i][j].begin(); iter != tree[i][j].end(); ++iter) {
				if (land[i][j] - *iter < 0) {
					sum += (*iter) / 2;
					dead_num++;
					ans--;
				}
				else {
					land[i][j] -= (*iter);
					(*iter)++;
				}
			}
			for (int k = 0; k < dead_num; ++k) tree[i][j].pop_back();
			land[i][j] += sum;
		}
	}
	// 가을, 겨울
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			for (auto iter = tree[i][j].begin(); iter != tree[i][j].end(); ++iter) {
				if ((*iter) % 5 == 0) {
					for (int dir = 0; dir < 8; ++dir) {
						int r = i + dx[dir];
						int c = j + dy[dir];
						if (r <= -1 || c <= -1 || r >= N || c >= N) continue;
						tree[r][c].push_front(1);
						ans++;
					}
				}
			}
			land[i][j] += A[i][j];
		}
	}
}
int main() {
	Input();
	while (K--) {
		Task();
	}
	cout << ans << "\n";
	return 0;
}