[백준] 16235번 나무 재테크

16235번 나무 재테크

---

1. 이해하기

• 처음에 모든 칸에는 5만큼의 양분이 들어있다.
• 사계절마다 일어나는 일이 다르다.
  • 봄에는 나무가 자신의 나이만큼 양분을 먹고, 나이가 1 증가한다. 이때 나무는 심어져있는 칸의 양분만 먹을 수 있다. 칸에 여러 개의 나무가 있다면, 나이가 어린 나무부터 양분을 먹는다. 땅에 양분이 자신의 나이만큼 이상이 없다면 나무는 죽는다.
  • 여름에는 봄에 죽은 나무가 양분으로 변한다. 죽은 나무마다 나이를 2로 나눈 값이 나무가 있던 칸에 양분으로 추가된다. 소수점 아래는 버린다.
  • 가을에는 나무가 번식한다. 번식하는 나무는 나이가 5의 배수이어야 한다. 번식은 인접한 8개의 칸에 나이가 1인 나무로 번식된다.
  • 겨울에는 S2D2가 땅을 돌아다니면서 땅에 양분을 추가한다.

---

2. 구현하기

• 현재 살아있는 나무와 죽은 나무를 구별해서 저장한다.

  • 덱을 사용하는 이유는 새로 추가된 나무를 앞에 추가하여 양분을 먹을 때 먼저 먹을 수 있도록 함이다.

• 각 계절마다 일어나는 일을 구현해준다.

  void spring() {
      for(int i = 0; i < N; i++) {
          for(int j = 0; j < N; j++) {
              int size = tree[i][j].size();
              for(int k = 0; k < size; k++) {
                  int age = tree[i][j].front(); tree[i][j].pop_front();
                  if(map[i][j] >= age) {
                      map[i][j]-=age;
                      age++;
                      tree[i][j].push_back(age);
                  } else {
                      die_tree[i][j].push_back(age);
                  }
              }
          }
      }
  }
  
  void summer() {
      for(int i = 0; i < N; i++) {
          for(int j = 0; j < N; j++) {
              while(!die_tree[i][j].empty()) {
                  int age = die_tree[i][j].front(); die_tree[i][j].pop_front();
                  map[i][j] += age/2;
              }
          }
      }
  }
  
  void autumn() {
      deque<int> next_tree[N][N];
      for(int i = 0; i < N; i++) {
          for(int j = 0; j < N; j++) {
              int size = tree[i][j].size();
              for(int k = 0; k < size; k++) {
                  int age = tree[i][j].front(); tree[i][j].pop_front();
                  if(age%5==0) {
                      for(int d = 0; d < 8; d++) {
                          int nx = i+dx[d], ny = j+dy[d];
                          if(nx < 0 or nx >= N or ny < 0 or ny >= N) continue;
                          next_tree[nx][ny].push_back(1);
                      }
                  }
                  tree[i][j].push_back(age);
              }
          }
      }
      for(int i = 0; i < N; i++) {
          for(int j = 0; j < N; j++) {
              while(!next_tree[i][j].empty()) {
                  int age = next_tree[i][j].front(); next_tree[i][j].pop_front();
                  tree[i][j].push_front(age);
              }
          }
      }
  }
  
  void winter() {
      for(int i = 0; i < N; i++) {
          for(int j = 0; j < N; j++) {
              map[i][j] += food[i][j];
          }
      }
  }

• K년 후에 살아남은 나무의 수를 반환한다.

  int simulate() {
      for(int i = 0; i < K; i++) {
          spring();
          summer();
          autumn();
          winter();
      }
      int ret = 0;
      for(int i = 0; i < N; i++) {
          for(int j = 0; j < N; j++) {
              ret += tree[i][j].size();
          }
      }
      return ret;
  }

---

3. 전체 코드

• 각 칸에 대해서 나무를 저장해준다. 이렇게 하지 않으면 시간 초과가 난다.

#include <iostream>
#include <deque>
using namespace std;
int map[10][10];
int food[10][10];
deque<int> tree[10][10];
deque<int> die_tree[10][10];
int dx[] = {-1,-1,-1,0,0,1,1,1};
int dy[] = {-1,0,1,1,-1,-1,0,1};
int N,M,K;

void spring() {
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            int size = tree[i][j].size();
            for(int k = 0; k < size; k++) {
                int age = tree[i][j].front(); tree[i][j].pop_front();
                if(map[i][j] >= age) {
                    map[i][j]-=age;
                    age++;
                    tree[i][j].push_back(age);
                } else {
                    die_tree[i][j].push_back(age);
                }
            }
        }
    }
}

void summer() {
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            while(!die_tree[i][j].empty()) {
                int age = die_tree[i][j].front(); die_tree[i][j].pop_front();
                map[i][j] += age/2;
            }
        }
    }
}

void autumn() {
    deque<int> next_tree[N][N];
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            int size = tree[i][j].size();
            for(int k = 0; k < size; k++) {
                int age = tree[i][j].front(); tree[i][j].pop_front();
                if(age%5==0) {
                    for(int d = 0; d < 8; d++) {
                        int nx = i+dx[d], ny = j+dy[d];
                        if(nx < 0 or nx >= N or ny < 0 or ny >= N) continue;
                        next_tree[nx][ny].push_back(1);
                    }
                }
                tree[i][j].push_back(age);
            }
        }
    }
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            while(!next_tree[i][j].empty()) {
                int age = next_tree[i][j].front(); next_tree[i][j].pop_front();
                tree[i][j].push_front(age);
            }
        }
    }
}

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

int simulate() {
    for(int i = 0; i < K; i++) {
        spring();
        summer();
        autumn();
        winter();
    }
    int ret = 0;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            ret += tree[i][j].size();
        }
    }
    return ret;
}

int main() {
    cin >> N >> M >> K;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> food[i][j];
            map[i][j] = 5;
        }
    }
    for(int i = 0; i < M; i++) {
        int x,y,age;
        cin >> x >> y >> age;
        x--; y--;
        tree[x][y].push_back(age);
    }

    cout << simulate() << '\n';
    return 0;
}