16235번-나무재테크

문제

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

16235번: 나무 재테크

---

접근방법

1) 접근 사고

그대로 구현하면 되는 문제였습니다. 저는 봄을 구현하는 과정에서 잘못된 구현으로 시간을 많이 낭비하였습니다. 양분을 먹고 새로 추가해주는 과정에서 새로운 배열에 담은 뒤에 기존 배열을 갱신해야하는데 그렇게 하지 않고 같은 배열에 두고 값을 넣어서 죽은 나무, 갱신 전에 나무의 값이 남아있어서 틀린 답이 나왔습니다. 이 부분을 제외한 계절의 구현은 정확히 구현하였습니다.

 

2) 시간 복잡도

O(n^2)

 

3) 배운 점

인구이동문제와 같은 실수를 했다. 

 

4) PS

아니 하;;;

---

정답 코드

#include<bits/stdc++.h>
 
using namespace std;
const int MAX = 11;
 
int A[MAX][MAX];
int board[MAX][MAX];
int N, M, K;
using vi = vector<int>;
using vvi = vector<vi>;
 
int my[] = {-1,-1,-1,0,0,1,1,1};
int mx[] = {-1,0,1,-1,1,-1,0,1};
 
int main(){
    cin >> N >> M >> K;
 
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++)ㅌ
            cin >> A[i][j];
            board[i][j] = 5;
        }
    }
    vector<vvi> tree(N, vvi(N));
    for(int i =0; i < M; i++){
        int y, x, value;
        cin >> y >> x >> value;
        tree[y-1][x-1].push_back(value);
 
    }
 
    while(K--){
        //정렬
        for(int i = 0; i< N; i++){
            for(int j = 0; j < N; j++){
                sort(tree[i][j].begin(), tree[i][j].end());
            }
        }
        //봄
        vector<vvi> dT(N, vvi(N));
 
        for(int i = 0; i < N; i++){
            for(int j= 0; j < N; j++){
                vector<int> tmp;
                for(auto &t : tree[i][j]){
                    if(board[i][j] >= t){
                        board[i][j] -= t;
                        tmp.push_back(t + 1);
                    }
                    else
                       dT[i][j].push_back(t);
                }
                tree[i][j].clear();
                for(int cur : tmp)
                    tree[i][j].push_back(cur);
            }
        }
        //여름
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                for(auto &dt : dT[i][j]){
                    board[i][j] += dt / 2;
                }
            }
        }
       // cout << "braek4" <<"\n";
        //가을
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                for(auto &t : tree[i][j]){
                   if((t % 5) == 0){
                       for(int d = 0; d < 8; d++){
                           int ny = i + my[d];
                           int nx = j + mx[d];
                           if(ny >= 0 && ny < N && nx >= 0 && nx < N){
                               tree[ny][nx].push_back(1);
                           }
                       }
                   }
                }
            }
        }
       // cout << "braek" <<"\n";
        //겨울
        for(int i =0; i < N; i++){
            for(int  j = 0; j< N; j++){
                board[i][j] += A[i][j];
            }
        }
    }
 
    int cnt = 0;
    for(int i =0; i < N; i++){
        for(int j =0; j< N; j++){
            for(auto t : tree[i][j])
                cnt++;
        }
    }
    cout << cnt <<"\n";
}