백준 16235 - 나무 재테크

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

16235번: 나무 재테크

문제 설명

---

 N×N 크기의 땅을 구매했다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 떨어진 칸의 개수, c는 가장 왼쪽으로부터 떨어진 칸의 개수이다. r과 c는 1부터 시작한다. 가장 처음에 양분은 모든 칸에 5만큼 들어있다.

 

상도는 나무 재테크로 더 큰 돈을 벌기 위해 M개의 나무를 구매해 땅에 심었다.

같은 1×1 크기의 칸에 여러 개의 나무가 심어져 있을 수도 있다.

 

이 나무는 사계절을 보내며, 아래와 같은 과정을 반복한다. RULE

 

(Spring)

나무가 자신의 나이만큼 양분을 먹고, 나이가 1 증가한다.

각각의 나무는 나무가 있는 1×1 크기의 칸에 있는 양분만 먹을 수 있다.

하나의 칸에 여러 개의 나무가 있다면, 나이가 어린 나무부터 양분을 먹는다. 만약, 땅에 양분이 부족해 자신의 나이만큼 양분을 먹을 수 없는 나무는 양분을 먹지 못하고 즉시 죽는다.

(Summer)

봄에 죽은 나무가 양분으로 변하게 된다. 각각의 죽은 나무마다 나이를 2로 나눈 값이 나무가 있던 칸에 양분으로 추가된다.

(Fall)

나무가 번식한다. 번식하는 나무는 나이가 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) 이다. 상도의 땅을 벗어나는 칸에는 나무가 생기지 않는다.

(Winter)

겨울에는 S2D2가 땅을 돌아다니면서 땅에 양분을 추가한다. 각 칸에 추가되는 양분의 양은 A[r][c]이다.

K년이 지난 후 상도의 땅에 살아있는 나무의 개수를 구하라~~

 

 

접근 방법

---

봄, 여름, 가을, 겨울 순서대로 작동되는 함수를 만들면 끝납니다~@.@, 근데 저는 시간 초과가 한번 나와서 방법을 바꾸어 진행했습니다.

두 코드 둘다 올려드릴게요 ~ 흐름은 비슷합니다. 

HINT: 하나의 격자판에 여러개의 나무가 들어갈 수 있다고 했으니 배열접근 보다는 백터로 접근하는게 좋겠죠~ ^0^

 

 

코드

---

//========================== 시간초과 해결된 풀이 ====================
#include <iostream>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
#define tree_food 101

using namespace std;
int N,M,K;
int map[11][11];
int dx[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int dy[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
vector<int>tree[11][11];
int insert_energy[11][11];
int energy[11][11];
int ans=0;
void springNsummer(){
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            if(tree[i][j].size()==0)continue;
            int die_to_energy=0;
            vector<int>tmp;
            sort(tree[i][j].begin(),tree[i][j].end());
            for(int k=0;k<tree[i][j].size();k++){
                int Age = tree[i][j][k];
                if(energy[i][j]>=Age){
                    energy[i][j]-=Age;
                    tmp.push_back(Age+1);
                }
                else{
                    die_to_energy+=(Age/2);
                }
            }
            tree[i][j].clear();
            for(int a=0;a<tmp.size();a++){
                tree[i][j].push_back(tmp[a]);
            }           
            energy[i][j]+=die_to_energy;
        }
    }
    
}
bool inside(int x,int y){
    return x>=1&&x<=N&&y>=1&&y<=N;
}
void fall(){
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            if(tree[i][j].size()==0)continue;
            for(int k=0;k<tree[i][j].size();k++){
                int Age = tree[i][j][k];
                if(Age%5==0){
                    for(int u=0;u<8;u++){
                        int nx=i+dx[u];
                        int ny=j+dy[u];
                        if(inside(nx,ny)){
                            tree[nx][ny].push_back(1);
                        }
                    }
                }
            }
        }
    }
}
void winter(){
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            energy[i][j]+=insert_energy[i][j];
        }
    }
}

int main(void){
    cin>>N>>M>>K;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            cin>>insert_energy[i][j];
            energy[i][j]=5;
        }
    }
    for(int i=0;i<M;i++){
        int r,c,s;
        cin>>r>>c>>s;
        tree[r][c].push_back(s);
    }
    while(K--){
        springNsummer();
        fall();
        winter();
    }
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            ans+=tree[i][j].size();
        }
    }
    cout<<ans;
}

//========================== 시간초과 발생한 풀이 ㅠㅠ ====================
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
typedef struct{
    int y,x;
    int age;
    int death;
}Tree;

int n,m,k;
int add_map[11][11];
int map[11][11];
vector<Tree>trees;
int dy[]={-1,-1,-1,0,0,1,1,1};
int dx[]={-1,0,1,-1,1,-1,0,1};

bool compare(Tree t1,Tree t2){
    if(t1.age<t2.age) return true;
    else return false;
}
//봄에는 나무가 자신의 나이만큼 양분을 먹고, 나이가 1 증가한다. 
//각각의 나무는 나무가 있는 1×1 크기의 칸에 있는 양분만 먹을 수 있다. 
//하나의 칸에 여러 개의 나무가 있다면, 나이가 어린 나무부터 양분을 먹는다. 
//만약, 땅에 양분이 부족해 자신의 나이만큼 양분을 먹을 수 없는 나무는 양분을 먹지 못하고 즉시 죽는다.
void spring(){
    sort(trees.begin(),trees.end(),compare);
    for(int i=0;i<trees.size();i++){
        if(trees[i].age==0)continue;
        int y = trees[i].y;
        int x = trees[i].x;
        int tree_Age = trees[i].age;
        if(map[y][x]>=tree_Age){
            map[y][x]-=tree_Age;
            trees[i].age++;
        }
        else{
            trees[i].death=1;
        }
    }
}
//여름에는 봄에 죽은 나무가 양분으로 변하게 된다. 
//각각의 죽은 나무마다 나이를 2로 나눈 값이 나무가 있던 칸에 양분으로 추가된다. 소수점 아래는 버린다.
void summer(){
    for(int i=0;i<trees.size();i++){
        if(trees[i].death==1){
            map[trees[i].y][trees[i].x]+=(floor(trees[i].age/2));
            trees[i].age=0;
        } 
    }
}
//가을에는 나무가 번식한다. 
//번식하는 나무는 나이가 5의 배수이어야 하며, 인접한 8개의 칸에 나이가 1인 나무가 생긴다. 
//상도의 땅을 벗어나는 칸에는 나무가 생기지 않는다.
void fall(){
    for(int i=0;i<trees.size();i++){
        if(trees[i].age==0)continue;
        else if(trees[i].age%5==0 && trees[i].death==0){
            int y = trees[i].y;
            int x = trees[i].x;
            for(int i=0;i<8;i++){
                Tree tree;
                tree.y = y+dy[i];
                tree.x = x+dx[i];
                tree.age=1; tree.death=0;
                if((tree.y>0&&tree.x>0)&&(tree.y<=n&&tree.x<=n)){
                    trees.push_back(tree);
                }
                else continue;
            }
        }
    }
}
void winter(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            map[i][j]+=add_map[i][j];
        }
    }
}
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>add_map[i][j];
            map[i][j]=5;
        }
    }
    for(int i=0;i<m;i++){
        Tree tree;
        cin>>tree.y>>tree.x>>tree.age;
        tree.death=0;
        trees.push_back(tree);
    }
    while(k--){
        spring();
        summer();
        fall();
        winter();
        
    }
    int ans=0;
    for(int i=0;i<trees.size();i++){
        if(trees[i].death==0) ans++;
    }
    cout<<ans<<"\n";
    return 0;
}

funny algorithms~ 0-0 ;;