[백준 16235] 나무 재테크

www.acmicpc.net/problem/16235

16235번: 나무 재테크

어렵진 않았는데 조건이 너무 복잡했던 문제..

봄+여름/ 가을/ 겨울로 나눠준다.

 

가을 겨울은 상대적으로 쉬우니까 패스

봄이랑 여름이 같이 구현되는게 편하다.

 

이 때 주의할 점은 

1. 봄에 양분을 먹고 나이가 증가한다는 점

2. 죽은 나무가 주는 양분은 나무가 전부 죽은 후 생긴다는 점: 여름에 죽은 나무가 양분이 되기 때문

이 두 가지를 체크해야 한다.

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int n, m, k;
int arr[10][10];
int fert[10][10];

int dr[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dc[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

vector<int> trees[10][10];

int tree;

void SpringAndSummer()
{
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < n; j++)
    {
      sort(trees[i][j].begin(), trees[i][j].end());
      int dieEnergy = 0;
      for (int k = 0; k < trees[i][j].size(); k++)
      {
      //양분이 나무나이보다 많으면
        if (arr[i][j] >= trees[i][j][k])
        {
          arr[i][j] -= trees[i][j][k]; //양분을 먹고
          trees[i][j][k]++; // 한살 증가
        }
        else
        {
        //소팅했으므로 뒤에 나무는 양분 전부 불가능. 전부 팝해준다.
          int smaller = k;
          for (int q = trees[i][j].size() - 1; q >= smaller; q--)
          {
            dieEnergy += trees[i][j][q] / 2;
            trees[i][j].pop_back();
            tree--;
          }
          break;
        }
      }
      arr[i][j] += dieEnergy; //여름에 죽은 나무가 양분으로 변하므로 마지막에 해야함
    }
  }
}

void Fall()
{
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < n; j++)
    {
      for (int k = 0; k < trees[i][j].size(); k++)
      {

        if (trees[i][j][k] % 5 == 0)
        {
          for (int q = 0; q < 8; q++)
          {
            int nr = i + dr[q];
            int nc = j + dc[q];

            if (nr < 0 || nc < 0 || nr > n - 1 || nc > n - 1)
            {
              continue;
            }
            trees[nr][nc].push_back(1);
            tree++;
          }
        }
      }
    }
  }
}

void Winter()
{
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < n; j++)
    {
      arr[i][j] += fert[i][j];
    }
  }
}

int main(void)
{
  scanf("%d%d%d", &n, &m, &k);

  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < n; j++)
    {
      arr[i][j] = 5;
      scanf("%d", &fert[i][j]);
    }
  }
  tree = m;

  for (int i = 0; i < m; i++)
  {
    int x, y, z;
    scanf("%d%d%d", &x, &y, &z);

    trees[x - 1][y - 1].push_back(z);
  }

  while (k--)
  {
    SpringAndSummer();
    Fall();
    Winter();
  }
  printf("%d\n", tree);
  return 0;
}