[백준 16235] 나무 재테크

문제: https://www.acmicpc.net/problem/16235

1)문제 분류

-시뮬레이션

2)문제해결

- 하란대로만 하면 정말 어려운 문제가 아닌데...

  1*1에 나무들이 계속 심어지니까 문제를 읽고 고민을 하게된다.. 시간 복잡도랑 메모리가 터지지는않을지..?ㅋㅋ

- 내가 구현한 방식은 

1*1 에 나무가 계속해서 심어지는 것은 vector에 map[][]을 선언해서 나무들을 심도록한다.

봄: 맵을 탐색하면서 나무가 심어진 부분을 보고 , 심어진 나무의 나이대로 정렬을 한다.      

       나이가 어린나무부터 양분을 먹기때문에, 나이기준 오름차순으로 나무를 정렬을 한 후에 토지의 양분을 섭취하도록한다.

       토지의 양분을 먹은 나무는 나이가 +1 되고, 이때 가을에 번식을 할수있다면, 즉 나이가 5의 배수라면 Fall(vector)에 삽입

       토지의 양분을 못먹은 나무는 죽게된다. 죽은나무는 여름에 양분이 되므로 Summer(vector)에 삽입

여름: 봄에서 탐색한 것을 기반으로 만들어진 Summer의 데이터를 기반으로 토지에 양분을 채워준다.

가을: 이것도 마찬가지로 봄에 탐색한것을 기반으로 만들어진 Fall의 데이터를 보고 8방향에 나무들을 번식 시켜준다.

겨울: 양분 공급

-위의 과정이 1년이므로 K만큼 위의 행위를 반복하고, Map[][]에 Size()를 구하면 총 나무의 개수를 알 수 있다.

//1시 45분 나무재테크- 2시 45분 구현 완료 

#include<iostream>

#include<vector>

#include<cstring>

#include<algorithm>

using namespace std;

int N, M, K;

vector<int>Map[12][12];//나무심어져있는상태

int Fill[12][12];//양분 맵

int CurFill[12][12];//현재토지상태

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

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

typedef struct Data

{

int age, x, y;

}Data;

vector<Data>Summer, Fall;

bool cmp(int a, int b)

{

return a <b;

}

bool range(int rx, int ry)

{

if (rx<1 || ry<1 || rx>N || ry>N)return false;

else return true;

}

int main()

{

scanf("%d %d %d", &N, &M, &K);

for (int i = 1; i <= N; i++)

{

for (int j = 1; j <= N; j++)

{

scanf("%d", &Fill[i][j]);

CurFill[i][j] = 5;

}

}

int x, y, z;

for (int i = 0; i < M; i++)

{

scanf("%d %d %d", &x, &y, &z);

Map[x][y].push_back(z);

}

while (K--)

{

//봄

for (int i = 1; i <= N; i++)

{

for (int j = 1; j <= N; j++)

{

if (Map[i][j].size() > 0)

{

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

int Len = Map[i][j].size();

vector<int>temp = Map[i][j]; 

Map[i][j].clear(); //새로 셋팅해야되니 클리어 

//cout << "개수: "<< temp.size() << endl;

for (int z = 0; z < Len; z++)

{

//cout << temp[z] << endl;

if (CurFill[i][j]- temp[z]>=0)

{

CurFill[i][j] -= temp[z]; //나이만큼 양분먹기

Map[i][j].push_back(temp[z] + 1);//나이 +1해서 심기

if ((temp[z] + 1) % 5 == 0) //5의 배수이면 가을에 나무번식 

{

Fall.push_back({ 0, i, j });

}

}

else //양분 못먹어서 죽은 나무들 

{

Summer.push_back({ temp[z] / 2,i,j });

}

}

}

}

}

//여름

for (int i = 0; i < Summer.size(); i++)

{

CurFill[Summer[i].x][Summer[i].y] += Summer[i].age;//여름에 죽은양분 더해주기 

}

Summer.clear(); //양분심어주고 클리어

//가을

for (int i = 0; i < Fall.size(); i++)

{

for (int d = 0; d < 8; d++)

{

int x = Fall[i].x+Dx[d];

int y = Fall[i].y+Dy[d];

if (range(x, y))

{

Map[x][y].push_back(1); //나이 1 나무번식

}

}

}

Fall.clear();//가을 클리어

//겨울 -양분공급 

for (int i = 1; i <= N; i++)

{

for (int j = 1; j <= N; j++)

{

CurFill[i][j] += Fill[i][j];

}

}

}

//나무개수구하기

int sum = 0;

for (int i = 1; i <= N; i++)

{

for (int j = 1; j <= N; j++)

{

sum += Map[i][j].size();

}

}

printf("%d\n", sum);

}