[BOJ] 나무 재테크 - 16235

Kyeongmin·2021년 10월 6일
0

알고리즘

목록 보기
13/24

📃 문제

[BOJ] 소문난 칠공주 🔗링크


❓ 문제 접근


🧠 풀이

#include <iostream>
#include <deque>
#include <utility>
#include <algorithm>

using namespace std;

int supply[11][11] = {0,};
int food[11][11] = {0,};

deque<pair<pair<int,int>,int>> trees;
deque<pair<pair<int,int>,int>> deadTrees;
deque<pair<pair<int,int>,int>> breedingTrees;

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

int main(int argc, const char * argv[]) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N,M,K;
    cin >> N >> M >> K;
    
    for(int r=0; r<N; r++){
        for(int c=0; c<N; c++){
            cin >> supply[r][c];
            food[r][c] = 5;
        }
    }
    
    for(int i=0; i<M; i++){
        int x,y,z;
        cin >> x >> y >> z;
        trees.push_back({{x-1,y-1},z});
    }
    sort(trees.begin(), trees.end());
    
    for(int year=0; year<K; year++){
        //spring
        int treeCount = trees.size();
        for(int i=0; i<treeCount; i++){
            int x = trees.front().first.first;
            int y = trees.front().first.second;
            int age = trees.front().second;
            trees.pop_front();
            
            if(food[x][y] >= age){
                trees.push_back({{x,y},age+1});
                food[x][y] -= age;
            }
            
            else{
                deadTrees.push_back({{x,y,},age});
            }
        }
        
        //summer
        while(!deadTrees.empty()){
            int x = deadTrees.front().first.first;
            int y = deadTrees.front().first.second;
            int age = deadTrees.front().second;
            deadTrees.pop_front();
            
            food[x][y] += age / 2;
        }
        
        //fall
        treeCount = trees.size();
        for(int i=0; i<treeCount; i++){
            int x = trees[i].first.first;
            int y = trees[i].first.second;
            int age = trees[i].second;
            
            if(age%5 == 0){
                for(int dir=0; dir<8; dir++){
                    int nx = x + dx[dir];
                    int ny = y + dy[dir];
                    if(!(nx>=0 && nx<N && ny>=0 && ny<N))   continue;
                    breedingTrees.push_back({{nx,ny},1});
                }
            }
        }
        
        while(!breedingTrees.empty()){
            trees.push_front(breedingTrees.front());
            breedingTrees.pop_front();
        }
        
        for(int r=0; r<N; r++){
            for(int c=0; c<N; c++){
                food[r][c] += supply[r][c];
            }
        }
    }
   
    cout << trees.size();
    
    return 0;
}

profile
개발자가 되고 싶은 공장장이🛠

0개의 댓글