[BOJ/백준][Gold4] 16235 : 나무 재테크(C++)

www.acmicpc.net/problem/16235

16235번: 나무 재테크

 

 

[난이도] Gold4

[유형] 시뮬레이션 (삼성SW기출)

 

[풀이] 

우선순위 큐를 사용한 코드는 시간초과가 나서 vector+sort를 조합해서 A/C를 받았다. 나무가 생각보다 많이 만들어질 수 있어서 push,pop 과정에서 시간이 많이 드는 것 같다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int N,M,K;
long long ans;
int dy[8] = {1,-1,0,0,1,1,-1,-1};
int dx[8] = {0,0,1,-1,1,-1,-1,1};
vector<long long> tree[101][101];;
int A[101][101],yb[101][101],seed[101][101];
void feed(int y,int x){
    auto& tr = tree[y][x];
    vector<long long> tt;
    int tyb=0;
    for(int i=0;i<tr.size();i++){
        int age = tr[i];
        if(yb[y][x] >= age){
            yb[y][x]-=age;
            tt.push_back(age+1);
        }else{
            tyb += age/2;
        }        
    }
    tr = tt;
    yb[y][x] += tyb;
}

void expd(int y,int x){
    auto& tr = tree[y][x];
    for(int i=0;i<tr.size();i++){
        int age = tr[i];
        if(age%5==0){
            for(int i=0;i<8;i++){
                int ny = y+dy[i];
                int nx = x+dx[i];
                if(ny < 1 || nx < 1 || ny > N || nx > N) continue;
                seed[ny][nx]++;
            }   
        }        
    }
}
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",&A[i][j]);
            yb[i][j] = 5;
        }
    for(int i=0;i<M;i++){
        int y,x,z;
        scanf("%d%d%d",&x,&y,&z);
        tree[x][y].push_back(z);
    }
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++) sort(tree[i][j].begin(),tree[i][j].end());
        
    while(K--){
        for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++){
                feed(i,j);
                seed[i][j]=0;
            }
        }
        for(int i=1;i<=N;i++)
            for(int j=1;j<=N;j++) expd(i,j);

        for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++){
                for(int k=0;k<seed[i][j];k++) tree[i][j].push_back(1);
                sort(tree[i][j].begin(),tree[i][j].end());
                yb[i][j] += A[i][j];
                if(K==0) ans += tree[i][j].size();
            }
        }
    }
    printf("%d",ans);
}

 

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/16235.cpp