[백준] 16235. 나무 재테크

[문제]

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

16235번: 나무 재테크

[풀이]

N,M,K가 주어지고 K년 후에 남아있는 나무의 수를 출력하면 된다.

따라서 for 문을 K년 동안 돌리고 for문에서 봄, 여름, 가을, 겨울에 대한 함수를 호출했다.

 

봄 - 에는 나무가 영양분을 먹는다. 단, 한 좌표에 나무가 2개 이상이면 나이가 어린 순서부터 영양분을 먹는다.

영양분이 부족하다면 먹지 못하고 나무는 죽는다.

 

여름 - 봄에 죽은 나무가 양분으로 변하게 된다. 해당 좌표에 나이/2 만큼 양분을 남긴다.

 

가을 - 나이가 5의 배수인 나무가 번식한다.

 

겨울 - input으로 주어진 양분이 추가된다.

 

 

---

봄,여름에 대한 함수를 하나로 묶고 가을,겨울에 대한 함수를 하나로 묶었다.

map을 벡터로 선언해 해당 좌표에 존재하는 나무의 나이를  벡터에 저장해줬다.

 

봄,여름 함수에서는 해당 좌표에 나무가 존재한다면 양분을 먹는다.

( 하나의 좌표에 여러개의 나무가 존재한다면 나이순을 오름차순 정렬)

양분이 부족해 나무가 먹지 못한다면 해당 idx를 기준으로 뒤에 있는 나무들은 모두 죽게된다. ( 오름차순으로 정렬된 상태이므로)

 

가을, 겨울 함수에서는 map에 벡터 사이즈를 기준으로 나무가 존재한다면 나무의 나이가 5의 배수인지 확인

5의 배수라면 나무는 번식한다. 따라서 주변 좌표에 나이가 1인 나무를 추가.

또한 양분을 추가해준다.(겨울)

 

 

 

[코드]

 

 

 

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>

#define MAX 11

using namespace std;

int N,M,K;
int A[MAX][MAX]={0,};//추가되는 양분
int nutrient[MAX][MAX]={0,}; // 현재 양분
vector<int> map[MAX][MAX];

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

void SpringSummer()
{
    int visited[MAX][MAX]={0,}; // 현재 양분

    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            
            int _size = map[i][j].size();
            
            if(_size==0)    continue;
            else if(_size > 1)  sort(map[i][j].begin(), map[i][j].end());
            
            int idx=0;
            while(idx < _size){
                if(map[i][j][idx] <= nutrient[i][j]) {
                    nutrient[i][j]-=map[i][j][idx];
                    map[i][j][idx]++;
                }
                else    break;
                idx++;
            }
            
            if(idx != _size){
                
                for(int k=_size-1; k>=idx ; k--){
                    nutrient[i][j] += map[i][j][k]/2;
                    map[i][j].pop_back();
                    M--;
                }
            }
        }
    }
}

void FallWinter()
{
    int num = M;
    
    for(int i=1;i<=N;i++){
        for(int j=1;j<= N;j++){
            if(map[i][j].size() ==0)    continue;
            
            for(int k=0;k<map[i][j].size();k++){
                int age = map[i][j][k];
                
                if(age%5 == 0){
                    for(int l=0;l<8;l++){
                        int nx = i + dx[l];
                        int ny = j + dy[l];
                        
                        if(nx < 1 || ny < 1 || nx > N || ny > N)    continue;
                        
                        map[nx][ny].push_back(1);
                        M++;
                    }
                }
            }
        }
    }

    
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++)   nutrient[i][j]+=A[i][j];
    }
}

int main(void)
{
    scanf("%d %d %d",&N,&M,&K);
    
    for(int i=1;i<=N;i++){
        for(int j=1; j<= N;j++) scanf("%d",&A[i][j]);
    }
    
    for(int i=1;i<=N;i++){
        for(int j=1; j<= N;j++) nutrient[i][j]=5;
    }
    
    for(int i=0;i<M;i++)
    {
        int x,y,age;
        scanf("%d %d %d",&x,&y,&age);
        map[x][y].push_back(age);
    }
    
    for(int i=0;i<K;i++){
        SpringSummer();
        FallWinter();
    }
    
    printf("%d",M);
    return 0;
    
}

 

지적, 조언, 질문 환영입니다.

댓글 남겨주세요~