나무 재테크 16235

문제

접근 방법

봄, 여름, 가을, 겨울을 나눠서 할 필요는 없지만 나누는 편이 더 보기 편할 것 같다.

봄에는 나이가 낮은 나무부터 양분을 흡수하여 크고 흡수하지 못하면 죽는 것이다.
여름에는 죽은 나무를 활용하여 양분을 만들어 주면 된다.
즉 죽는 경우에 대해서도 저장해 줘야 한다.
가을에는 5의 배수인 나무의 주변에 나무를 심어주면 된다.
겨울에는 A값을 맵에 추가해 주면 된다.

구현 자체는 어렵지 않지만 시간 초과와 관련하여 추가로 생각해야 할 부분이 존재한다.

코드

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#include <deque>
using namespace std;

typedef tuple<int, int, int> tree; // 나이, 위치 (x, y)
vector<vector<int>> A, map;
vector<tree> dieTrees;
deque<tree> trees, nextTrees;

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

void spring()
{
    for (auto it = trees.begin(); it != trees.end(); ++it)
    {
        tree t = *it;

        int age = get<0>(t);
        int x = get<1>(t);
        int y = get<2>(t);

        if (map[x][y] >= age)
        {
            map[x][y] -= age;
            ++age;
            nextTrees.push_back({age, x, y});

            if (age % 5 == 0) // 가을 생략
            {
                for (int j = 0; j < 8; ++j)
                {
                    int nx = x + dx[j];
                    int ny = y + dy[j];

                    if (ny >= 0 && nx >= 0 && ny < N && nx < N)
                    {
                        nextTrees.push_front({1, nx, ny}); // 덱의 경우 앞, 뒤로 삽입 가능
                    }
                }
            }
        }
        else
        {
            dieTrees.push_back(t);
        }
    }
    trees.clear();
    trees.swap(nextTrees);
}

void summer()
{
    for (tree t : dieTrees)
    {
        int age = get<0>(t);
        int x = get<1>(t);
        int y = get<2>(t);

        map[x][y] += age / 2;
    }

    dieTrees.clear();
}

void winter()
{
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            map[i][j] += A[i][j];
        }
    }
}

void input()
{
    ios::sync_with_stdio(0), cin.tie(0);

    cin >> N >> M >> K;
    map = A = vector<vector<int>>(N, vector<int>(N, 5));

    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            cin >> A[i][j];
        }
    }

    for (int i = 0, x, y, z; i < M; ++i)
    {
        cin >> x >> y >> z;
        --x;
        --y;
        trees.push_back({z, x, y});
    }
    sort(trees.begin(), trees.end());
}

void solve()
{
    while (K--)
    {
        spring();
        summer();
        winter();
    }
    cout << trees.size();
}

int main()
{
    input();
    solve();
    return 0;
}

풀이

deque를 사용하면 시간을 절약할 수 있다.
나무는 나이를 1씩 먹기에 한번 정렬해 둔 순서가 바뀔 일은 없다.
그리고 새로운 나무 또한 앞으로 추가하면 정렬을 뒤바꾸지 않는다.

해당 부분은 자력으로 생각해 내지 못하였다. 시간 초과가 났을 때 가을을 봄에 합쳐서 시도했었는데 시간을 줄일 수 있긴 했지만, 시간초과는 해결하지 못했다.
deque이 결정적이었던 것 같다.

추가로 2차원 배열을 사용하여 deque을 좌표마다 활용해 준다면 죽은 나무를 따로 저장할 필요 없이 죽은 나무의 합산을 마지막에 더해주면 된다.
즉 여름을 봄에 합칠 수 있는 것이다.