[백준 16235] 나무 재테크

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

16235번: 나무 재테크

요구사항

k 시간 지난 후, 나무 개수 구하기

 

풀이

1. 봄, 여름, 가을, 겨울의 조건대로 구현한다

2. 봄에 먹이를 줄때, 여름의 경우를 같이 처리해준다

3. 5의 배수일때 번식을 하므로, 이 경우도 고려해서 처리한다.

 

#include<iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <string.h>

using namespace std;

//priority_queue<int,vector<int>,greater<>> map[11][11];
vector<int> map[11][11];
int visit[11][11];
int eat[11][11];
int now[11][11];
int dr[8] = { -1,-1,-1,0,1,1,1,0 };
int dc[8] = { -1,0,1,1,1,0,-1,-1 };
int n, m, k;
int ans = 0;
void show() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << map[i][j].size() << " ";
        }
        cout << endl;
    }
    cout << endl;
}
bool com(int a, int b) {
    if (a > b) return true;
    return false;

}
void solve() {
    while (k--) {
       // show();
        memset(visit, 0, sizeof(visit));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j].size() > 0) {

                    vector<int> nq;
                    
                    sort(map[i][j].begin(), map[i][j].end(), com);

                    int s = map[i][j].size();
                    int tempsum = 0;
                    //크기만큼

                    for (int k = 0; k < s; k++) {
                        int nowtop = map[i][j].back();
                        if (now[i][j] - nowtop >= 0) {
                       
                            map[i][j].pop_back();
                            now[i][j] = now[i][j] - nowtop;
                            nq.push_back(nowtop + 1);
                         
                            if (nowtop != 0 && (nowtop + 1) % 5 == 0) {
                                visit[i][j]++;
                            }
                        }
                        else {
                            map[i][j].pop_back();
                            int temp = nowtop / 2;
                            tempsum += temp;
                        }
                    }
                    map[i][j] = nq;

                    now[i][j] += tempsum;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                now[i][j] += eat[i][j];
                if (visit[i][j] > 0) {
                    for (int k = 0; k < visit[i][j]; k++) {
                        for (int a = 0; a < 8; a++) {
                            int nr = i + dr[a];
                            int nc = j + dc[a];
                            if (nr < 0 || nc < 0 || nr >= n || nc >= n)
                                continue;
                            map[nr][nc].push_back(1);
                        }
                    }
                }
            }
        }

    }
    int sum = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {

            ans += map[i][j].size();
        }
        // cout<<endl;
    }

}

int main()
{
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> eat[i][j];
            now[i][j] = 5;
        }
    }
    for (int i = 0; i < m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        map[x - 1][y - 1].push_back(z);
    }

    solve();
    //  cout<<"B"<<endl;
    cout << ans << endl;
}