Baekjoon 16235번 나무 재테크

문제

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

걸린 시간

01 : 53 : 12 실패

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

struct node{
    int y, x, age;
    node(int y, int x, int age){
        this->y = y;
        this->x = x;
        this->age = age;
    }
};

int n, m, k;
int dy[8] = {-1, 1, 0, 0, 1, 1, -1, -1};
int dx[8] = {0, 0, -1, 1, 1, -1, 1, -1};
vector<vector<int>> A, land; // 겨울의 추가되는 양분, 현재 땅의 양분
vector<vector<vector<int>>> tree;

void breeding(int y, int x){
    for(int i = 0; i < 8; i++){
        int ny = y+dy[i];
        int nx = x+dx[i];
        if(0 <= ny && ny < n && 0 <= nx && nx < n)
            tree[ny][nx].push_back(1);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m >> k;
    A.resize(n, vector<int>(n));
    land.resize(n, vector<int>(n, 5));
    for(int y = 0; y < n; y++)
        for(int x = 0; x < n; x++)
            cin >> A[y][x];
    tree.resize(n, vector<vector<int>>(n));
    int y, x, z;
    for(int i = 0; i < m; i++){
        cin >> y >> x >> z;
        tree[y-1][x-1].push_back(z);
    }
    for(int i = 0; i < k; i++){
        vector<pair<int, int>> breed;
        // spring & summer
        for(int y = 0; y < n; y++)
            for(int x = 0; x < n; x++){
                sort(all(tree[y][x]));
                for(int j = 0; j < tree[y][x].size(); j++){
                    int age = tree[y][x][j];
                    if(land[y][x] >= age){
                        land[y][x] -= age;
                        age++;
                        tree[y][x][j] = age;
                        if(age%5 == 0) breed.push_back(make_pair(y, x));
                    }
                    else{
                        for(int k = j; k < tree[y][x].size(); k++)
                            land[y][x] += tree[y][x][k]/2;
                        tree[y][x].erase(tree[y][x].begin()+j, tree[y][x].end());
                        break;
                    }
                }
            }
        // fall
        for(int j = 0; j < breed.size(); j++)
            breeding(breed[j].first, breed[j].second);
        // winter
        for(int y = 0; y < n; y++)
            for(int x = 0; x < n; x++)
                land[y][x] += A[y][x];
    }
    int ans = 0;
    for(int y = 0; y < n; y++)
        for(int x = 0; x < n; x++)
            ans += tree[y][x].size();
    cout << ans << "\n";
    return 0;
}

엄청 쉬운 문제인 줄 알았는데 0.3초 시간제한이 많이 빡빡하다.

처음엔 나무를 최대 힙을 사용하여 관리했다. 모든 나무를 나이가 적은 순서대로 양분을 섭취해야하는 봄에 제일 많은 시간이 걸리는데, 모든 나무를 힙에서 꺼내고 살아남은 나무만 다시 힙에 넣어주어야 하므로 최악의 경우 O(2nlogn) 로 시간초과가 발생한다.

이를 선형 자료구조로 바꾼 후 정렬해서 사용하면 O(n + nlogn), 그 이하로 시간복잡도를 줄일 수 있다. 오름차순으로 정렬이 되어 있으면 양분을 섭취할 수 없는 나무 이후는 모두 죽게 되는 나무로 간주할 수 있기 때문이다.

참고

공손히 부탁드립니다.. 2주째 시간초과 제발 도와주세요