백준 마법사 상어와 파이어볼과 유사한 문제였다. 과거 해결했던 경험으로 골3 난이도에 비해 쉽게 문제를 풀어나갈 수 있었지만 한가지 문제점이 있었다.
Map에 심은 나무는 해당 지역 양분보다 나이가 많을 경우 죽어야 하는데, 이 죽을 경우 Map에서 죽은 나무를 치우는 방식을 생각하지 못했다. 그래서 죽은 나무의 나이를 -2로 설정하고 제출하니 죽은 나무를 모두 고려한 탓에 시간 초과가 나오게 되었다. 방법은 마법사 상어 해결 방식에 사용한 것 처럼 Map을 sort하고 해결한 나무는 vector 에 넣은 다음 map.clear를 통해 해당 맵을 지우고 죽지 않은 나무(vector)를 다시 map의 해당 구역에 넣어주는 방식 이였다.
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
struct TREE {
int age;
int x;
int y;
bool dead = false;
bool operator<(const TREE& other) const {
return age < other.age;
}
};
int n, m, k;
bool check[100][100] = { false };
//심어져 있는 나무
vector<int> map[100][100];
//겨울에 추가되는 비료
int fertilizer[100][100];
//현재 비료
int cur_fertilizer[100][100] = { 5 };
//묘목 정보
vector<TREE> tree;
int result = 0;
void input() {
cin >> n >> m >> k;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> fertilizer[i][j];
}
}
for (int i = 0; i < m; i++) {
//위치,위치,나이
int x, y, z;
cin >> x >> y >> z;
tree.push_back({ z ,x - 1, y - 1});
}
return;
}
//나무가 자신의 나이만큼 양분을 먹고, 나이가 1 증가한다.각각의 나무는 나무가 있는 1×1 크기의 칸에 있는 양분만 먹을 수 있다.
//하나의 칸에 여러 개의 나무가 있다면, 나이가 어린 나무부터 양분을 먹는다.
//만약, 땅에 양분이 부족해 자신의 나이만큼 양분을 먹을 수 없는 나무는 양분을 먹지 못하고 즉시 죽는다.
void spring() {
sort(tree.begin(), tree.end());
for (int i = 0; i < tree.size(); i++) {
int x = tree[i].x;
int y = tree[i].y;
int age = tree[i].age;
if (cur_fertilizer[x][y] - age > 0) {
//양분이 남아있기 때문에 현재 양분을 나무가 필요한 만큼 제외시킴
cur_fertilizer[x][y] -= age;
//나무가 양분을 먹었기 때문에 나이가 1 증가함
tree[i].age++;
}
else {
tree[i].dead = true;
//양분이 없으면 죽임
continue;
}
}
}
void summer() {
sort(tree.begin(), tree.end());
memset(check, false, sizeof(check));
//여름에는 봄에 죽은 나무가 양분으로 변하게 된다. 각각의 죽은 나무마다 나이를 2로 나눈 값이 나무가 있던 칸에 양분으로 추가된다. 소수점 아래는 버린다.
for (int i = 0; i < tree.size(); i++) {
int x = tree[i].x;
int y = tree[i].y;
//만약 죽은 나무 일시
if (tree[i].dead == true) {
//죽은 나무의 나이
int age = tree[i].age;
//현재 비료에 죽은 나무의 나이 /2값 추가
cur_fertilizer[x][y] += age / 2;
}
}
}
int dx[8] = { -1,-1,-1,0,0,1,1,1 };
int dy[8] = { -1,0,1,-1,1,-1,0,1 };
//가을에는 나무가 번식한다.번식하는 나무는 나이가 5의 배수이어야 하며,
//인접한 8개의 칸에 나이가 1인 나무가 생긴다.어떤 칸(r, c)와 인접한 칸은(r - 1, c - 1), (r - 1, c), (r - 1, c + 1), (r, c - 1), (r, c + 1), (r + 1, c - 1), (r + 1, c), (r + 1, c + 1)
//이다.상도의 땅을 벗어나는 칸에는 나무가 생기지 않는다.
void fall() {
for (int i = 0; i < tree.size(); i++) {
int x = tree[i].x;
int y = tree[i].y;
//번식 하는 나무는 나이가 5의 배수이여야 하고 죽은 나무가 아니여야 한다.
if (tree[i].dead == true|| tree[i].age % 5 != 0) continue;
for (int i = 0; i < 7; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
//상도의 칸을 벗어나면 안됨
if (0 <= nx && nx < n && 0 <= ny && ny < n) {
tree.push_back({ 1,nx, ny,false });
}
}
}
}
//겨울에는 S2D2가 땅을 돌아다니면서 땅에 양분을 추가한다. 각 칸에 추가되는 양분의 양은 A[r][c]이고, 입력으로 주어진다.
void winter() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cur_fertilizer[i][j] += fertilizer[i][j];
}
}
}
void solve() {
for (int i = 0; i < 4; i++) {
//봄
spring();
//여름
summer();
//가을
fall();
//겨울
winter();
}
for (int i = 0; i < tree.size(); i++) {
if (tree[i].age > 0 || tree[i].dead == false) {
result++;
}
}
cout << result;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
input();
solve();
return 0;
}#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
int dx[8] = { -1,-1,-1,0,0,1,1,1 };
int dy[8] = { -1,0,1,-1,1,-1,0,1 };
int n, m, k;
//심어져 있는 나무
vector<int> map[100][100];
//겨울에 추가되는 비료
int fertilizer[100][100];
//현재 비료
int cur_fertilizer[100][100];
//묘목 정보
int result = 0;
void input() {
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> fertilizer[i][j];
cur_fertilizer[i][j] = 5;
}
}
for (int i = 0; i < m; i++) {
//위치,위치,나이
int x, y, z;
cin >> x >> y >> z;
map[x][y].push_back(z);
}
return;
}
//나무가 자신의 나이만큼 양분을 먹고, 나이가 1 증가한다.각각의 나무는 나무가 있는 1×1 크기의 칸에 있는 양분만 먹을 수 있다.
//하나의 칸에 여러 개의 나무가 있다면, 나이가 어린 나무부터 양분을 먹는다.
//만약, 땅에 양분이 부족해 자신의 나이만큼 양분을 먹을 수 없는 나무는 양분을 먹지 못하고 즉시 죽는다.
void spring() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int dead_energy = 0;
vector<int> temp;
if (map[i][j].size() > 0) {
sort(map[i][j].begin(), map[i][j].end());
for (int z = 0; z < map[i][j].size(); z++) {
if (map[i][j][z] <= cur_fertilizer[i][j]) {
cur_fertilizer[i][j] -= map[i][j][z];
temp.push_back(map[i][j][z]+1);
}
//양분이 부족함
else {
dead_energy += map[i][j][z] / 2;
}
}
}
map[i][j].clear();
for (int z = 0; z < temp.size(); z++) {
map[i][j].push_back(temp[z]);
}
cur_fertilizer[i][j] += dead_energy;
}
}
}
//가을에는 나무가 번식한다.번식하는 나무는 나이가 5의 배수이어야 하며,
//인접한 8개의 칸에 나이가 1인 나무가 생긴다.어떤 칸(r, c)와 인접한 칸은(r - 1, c - 1), (r - 1, c), (r - 1, c + 1), (r, c - 1), (r, c + 1), (r + 1, c - 1), (r + 1, c), (r + 1, c + 1)
//이다.상도의 땅을 벗어나는 칸에는 나무가 생기지 않는다.
void fall() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (map[i][j].size() > 0) {
for (int z = 0; z < map[i][j].size(); z++) {
if (map[i][j][z] % 5 == 0) {
for (int e = 0; e < 8; e++) {
int nx = i + dx[e];
int ny = j + dy[e];
if (0 < nx && nx <= n && 0 < ny && ny <= n) {
map[nx][ny].push_back(1);
}
}
}
}
}
}
}
}
//겨울에는 S2D2가 땅을 돌아다니면서 땅에 양분을 추가한다. 각 칸에 추가되는 양분의 양은 A[r][c]이고, 입력으로 주어진다.
void winter() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cur_fertilizer[i][j] += fertilizer[i][j];
}
}
}
void solve() {
for (int i = 0; i < k; i++) {
//봄
spring();
//여름
//가을
fall();
//겨울
winter();
}
//살아 있는 나무 구하기
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (map[i][j].size() > 0) {
result += map[i][j].size();
}
}
}
cout << result;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
input();
solve();
return 0;
}