16235 나무 재테크

올해의 상황만이 내년에 영향을 미칠 수 있기 때문에 개수를 관리하는 배열과 현재 가지고 있는 나무 위치 q를 [2]로 만들었다.

대충 계산한 나무의 나이 최대치는 27

10 1 1000

100 100 100 100 100 100 100 100 100 100

100 100 100 100 100 100 100 100 100 100

100 100 100 100 100 100 100 100 100 100

100 100 100 100 100 100 100 100 100 100

100 100 100 100 100 100 100 100 100 100

100 100 100 100 100 100 100 100 100 100

100 100 100 100 100 100 100 100 100 100

100 100 100 100 100 100 100 100 100 100

100 100 100 100 100 100 100 100 100 100

100 100 100 100 100 100 100 100 100 100

1 1 5

max_year = 27

혹시몰라서 40으로 만들었다.

덱을 사용한 이유는 매년 살아남으면 나이가 +1이 되고 번식한다면 무조건 나이 1짜리가 더해지기 때문에

기존에 정렬된 상태라면 살아남은 경우는 다음해에 push_back, 번식하면 push_front하면 정렬이 그대로 유지되기 때문이다.

#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;
 
// x,y,나이
struct p {
    int x, y, c;
};
 
int n, m, k, idx, ni;
/* 
map = 현재 양분
ad    = 매년 더해지는 양분
d    = 올해 죽은 나무들로 인해 더해질 양분
*/
int map[10][10], ad[10][10], d[10][10];
// [cur][x][y][year] cur==0 ? cur_year : next_year
int cnt[2][10][10][40];
int dx[] = { -1,-1,0,1,1,1,0,-1 }, dy[] = { 0,1,1,1,0,-1,-1,-1 };
// 임시배열
p t[1000];
// [cur]
deque<p> q[2];
 
// 번식
void run(int x, int y, int c) {
    for (int i = 0; i < 8; ++i) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
        if (cnt[ni][nx][ny][1] == 0) 
            q[ni].push_front({ nx,ny,1 });
        cnt[ni][nx][ny][1] += cnt[idx][x][y][c];
    }
}
 
int main() {
    scanf("%d%d%d", &n, &m, &k);
 
    for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j)
        scanf("%d", &ad[i][j]), map[i][j] = 5;
 
    idx = (k + 1) % 2;
 
    for (int i = 0; i < m; ++i) {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        x--; y--;
        t[i] = { x,y,c };
        cnt[idx][x][y][c]++;
    }
 
    sort(t, t + m, [&](const p &a, const p &b) { return a.c < b.c; });
    
    for (int i = 0; i < m; ++i) q[idx].push_back(t[i]);
 
    while (k--) {
        idx = k % 2;
        ni = (k + 1) % 2;
        while (q[idx].size()) {
            int x = q[idx].front().x;
            int y = q[idx].front().y;
            int c = q[idx].front().c;
            q[idx].pop_front();
            // {x,y}위치의 나이 c인 나무들을 모두 감당하지 못함
            if (map[x][y] - c * cnt[idx][x][y][c] < 0) {
                // 다죽음
                if (map[x][y] < c) {
                    // 겨울에 더해질 양분
                    d[x][y] += (c / 2)*cnt[idx][x][y][c];
                    
                    cnt[idx][x][y][c] = 0;
                }
                // 일부는 살아남음
                else {
                    // 겨울에 더해질 양분
                    d[x][y] += (c / 2)*(cnt[idx][x][y][c] - map[x][y] / c);
 
                    q[ni].push_back({ x,y,c + 1 });
                    
                    cnt[ni][x][y][c + 1] = map[x][y] / c;
                    cnt[idx][x][y][c] = map[x][y] / c;
 
                    // 내년에 번식가능한 나이가 되면 번식
                    if ((c + 1) % 5 == 0)
                        run(x, y, c);
 
                    cnt[idx][x][y][c] = 0;
                }
                // 양분 소모
                map[x][y] %= c;
            }
            else {
                // 양분 소모
                map[x][y] -= c * cnt[idx][x][y][c];
 
                q[ni].push_back({ x,y,c + 1 });
                cnt[ni][x][y][c + 1] = cnt[idx][x][y][c];
 
                // 내년에 번식가능한 나이가 되면 번식
                if ((c + 1) % 5 == 0) 
                    run(x, y, c);
 
                cnt[idx][x][y][c] = 0;
            }
        }
        // 겨울
        for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) map[i][j] += ad[i][j] + d[i][j], d[i][j] = 0;
    }
 
    int ans = 0;
    while (q[1].size()) {
        ans += cnt[1][q[1].front().x][q[1].front().y][q[1].front().c];
        q[1].pop_front();
    }
    printf("%d\n", ans);
    return 0;
}