[BOJ] 16235 나무 재테크

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

16235번: 나무 재테크

 

처음 이 문제를 풀 때, priority queue를 이용하여 풀었는데 시간초과가 떴다.

이 문제는 삽입과 삭제가 여러 번 일어나는 문제인데, priority queue를 이용하면 삽입, 삭제가 일어날 때마다 O(logN)의 시간이 필요하게 된다. 

잘 생각해보면 처음 문제에서 값을 주어질 때를 제외하고는 반복문이 돌 때 배열에 값들이 작은 값에서 큰 값으로 입력된다. 따라서 처음에만 값들을 정렬해주고 deque를 이용하면 삽입, 삭제를 O(1)에 수행 할 수 있다.

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int N,M,K;
deque<int> dq[10][10];

int A[10][10];
int map[10][10];

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

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>N>>M>>K;
    
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            cin>>A[i][j];
            map[i][j]=5;
        }
    }
    
    int x,y,age;
    
    for(int i=0;i<M;i++){
        cin>>y>>x>>age;
        dq[y-1][x-1].push_back(age);
    }
    
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            sort(dq[i][j].begin(),dq[i][j].end(),greater<int>());
        }
    }
    
    while(K--){
        
        //봄,여름
        int a,b,index;
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                index=0;
                b=0;
                int s=dq[i][j].size();
                for(int k=0;k<s;k++){
                    a=dq[i][j].front();
                    dq[i][j].pop_front();
                    if(a<=map[i][j]){
                        map[i][j]-=a;
                        dq[i][j].push_back(a+1);
                    }else
                        b+=(a/2);
                }
                map[i][j]+=b;
            }
        }
        
        //가을
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                int s=dq[i][j].size();
                for(int k=0;k<s;k++){
                    a=dq[i][j].front();
                    dq[i][j].pop_front();
                    if(a%5==0){
                        for(int k=0;k<8;k++){
                            int ny=i+dy[k], nx=j+dx[k];
                            if(0<=ny&&ny<N&&0<=nx&&nx<N)
                                dq[ny][nx].push_front(1);
                        }
                    }
                    dq[i][j].push_back(a);
                }
            }
        }
        
        //겨울
        for(int i=0;i<N;i++)
            for(int j=0;j<N;j++)
                map[i][j]+=A[i][j];
    }
    
    int ans=0;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            while(!dq[i][j].empty()){
                dq[i][j].pop_front();
                ans++;
            }
        }
    }
    cout<<ans;
    return 0;
}