백준 16235번 나무 재테크 문제 풀이

백준저지 16235번 나무 재테크 문제 풀이입니다.

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

전형적인 구현 문제입니다.

벡터의 2차원 배열로 나무들을 표현했고, 나무의 나이를 매년 더하기 보다는, 사람 나이를 생년월일로 나타내듯,

탄생 년도와 현재 년도를 기준으로 나이를 표현해서 풀이해 보았습니다.

 

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

vector<int> birth[10][10];
int V[10][10]; //현재 양분
int A[10][10]; //추가하는 양분
int B[10][10]; //나무 죽어서 추가하는 양분
int n, m, k;

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

inline bool is_in(int x, int y) {
    return x >= 0 && y >= 0 && x < n && y < n;
}
#define FOR(i, a, b) for (int i=a; i < b; i++)
int main() {
    scanf("%d%d%d", &n, &m, &k);

    FOR(i, 0, n) {
        FOR(j, 0, n) {
            scanf("%d", &A[i][j]);
            V[i][j] = 5;
        }
    }
    FOR(i, 0, m) {
        int x, y, age;
        scanf("%d%d%d", &x, &y, &age);
        x--;
        y--;
        birth[x][y].push_back(-age);
    }

    FOR(year, 0, k) {
        //봄
        //나이 = year - birth
        //양분 먹음, 죽을 나무 결정
        FOR(i, 0, n) {
            FOR(j, 0, n) {
                if (birth[i][j].size()) {
                    sort(birth[i][j].begin(), birth[i][j].end(), greater<int>());
                    int death_count = 0;
                    FOR(l, 0, birth[i][j].size()) {
                        int age = year - birth[i][j][l];
                        if (V[i][j] >= age) {
                            V[i][j] -= age;
                        }
                        else {
                            death_count++;
                            B[i][j] += age / 2;
                        }
                    }
                    FOR(l, 0, death_count) {
                        birth[i][j].pop_back();
                    }
                }
            }
        }
        //여름
        //나이 = year - birth + 1;
        FOR(i, 0, n) {
            FOR(j, 0, n) {
                V[i][j] += B[i][j] + A[i][j];
                B[i][j] = 0;
                if (birth[i][j].size()) {
                    FOR(l, 0, birth[i][j].size()) {
                        int age = year - birth[i][j][l] + 1;
                        if (age % 5 == 0) {
                            FOR(d, 0, 8) {
                                int nx = i + dx[d];
                                int ny = j + dy[d];
                                if (is_in(nx, ny)) {
                                    birth[nx][ny].push_back(year);
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    int ans = 0;
    FOR(i, 0, n) {
        FOR(j, 0, n) {
            ans += birth[i][j].size();
        }
    }
    printf("%d\n", ans);
}