나무 재테크

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#include <map>
#define ll long long
using namespace std;
// 12:58 ~
int N,M,K,ans;
int origin[12][12];
queue<int> dead[12][12];
// 남은 양분, 나무들
pair<int,deque<int>> board[12][12];
bool check(int y, int x)
{
    if(x<0 or y<0 or x>=N or y>=N) return false;
    return true;
}
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 >> origin[i][j];
            board[i][j].first = 5;
        }
    for(int i=0;i<M;i++)
    {
        int r,c,age;
        cin >> r >> c >> age;
        board[r-1][c-1].second.push_back(age);
    }
    while(K--)
    {
        /* 봄 */
        for(int i=0;i<N;i++)
        {
            for(int j=0;j<N;j++)
            {
                int len = board[i][j].second.size();
                for(int k=0;k<len;k++)
                {
                    int cur = board[i][j].second.front(); board[i][j].second.pop_front();
                    if(board[i][j].first >= cur){
                        board[i][j].first -= cur;
                        board[i][j].second.push_back(++cur);
                    }else{
                        dead[i][j].push(cur);
                    }
                }
            }
        }
        /* 여름 */
        for(int i=0;i<N;i++)
        {
            for(int j=0;j<N;j++)
            {
                while(!dead[i][j].empty())
                {
                    int cur = dead[i][j].front(); dead[i][j].pop();
                    board[i][j].first += cur/2;
                }
            }
        }
        /* 가을 */
        for(int i=0;i<N;i++)
        {
            for(int j=0;j<N;j++)
            {
                int len = board[i][j].second.size();
                for(int k=0;k<len;k++)
                {
                    /* 나무의 나이가 5의배수이면 주변에 나무 번식 */
                    if(board[i][j].second[k]%5 == 0)
                    {
                        if(check(i-1,j-1))
                            board[i-1][j-1].second.push_front(1);
                        if(check(i-1,j))
                            board[i-1][j].second.push_front(1);
                        if(check(i-1,j+1))
                            board[i-1][j+1].second.push_front(1);
                        if(check(i,j-1))
                            board[i][j-1].second.push_front(1);
                        if(check(i,j+1))
                            board[i][j+1].second.push_front(1);
                        if(check(i+1,j-1))
                            board[i+1][j-1].second.push_front(1);
                        if(check(i+1,j))
                            board[i+1][j].second.push_front(1);
                        if(check(i+1,j+1))
                            board[i+1][j+1].second.push_front(1);
                    }
                }
            }
        }
        /* 겨울 */
        for(int i=0;i<N;i++)
            for(int j=0;j<N;j++)
                board[i][j].first += origin[i][j];
    }
    /* 살아남은 나무 개수 count */
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            ans += board[i][j].second.size();
    cout << ans;
    return 0;
}

• 최초 실패 원인
  : 최초 deque를 쓰지 않고, vector를 사용하면서 양분을 주기 전에 sort()를 했더니 시간초과 발생
  --> deque를 쓰면 앞,뒤에서 삭제가 O(1)밖에 안걸리며, 어차피 한번 양분을 못주면 알아서 나머지 뒤는 죽으니까 신경쓰지 않아도 된다

• 깨달은 것
  • vector<>와 sort대신 deque를 잘 쓰면 조건에 따라 정렬된 상태를 O(1)로 유지할 수 있음