[ 백준 16235 ] 나무 재테크

문제

문제로 이동

문제 설명

• 1 X 1 의 칸에 여러 나무들을 심을 수 있으므로 나무들의 나이를 모두 기억해야 합니다.

=> struct 기반의 2차원 배열을 사용

typedef sturct{
    int tree[2000];
    int size=-1; // tree의 index 용
    int yummy=5;//초반의 양분은 5로 setting
}TREE;
​
TREE arr[101][101];

 

입력받은 K년마다 봄, 여름 , 가을 , 겨을 을 겪으면서 나무 재테크(?)를 해야하는데, 봄 여름 과정을 통일 시킬 수 있습니다.

 

• 봄 , 여름

봄이 왔을 때, 나이가 적은 나무부터 양분을 섭취하게 되면 양분이 없어 나이가 많은 나무들은 죽게 됩니다. 이때,< 여기서 부터 여름 과정 > (죽은 나무들 / 2) 의 계산값을 변수에 모아두어 1X1칸의 봄 과정이 끝났을 때 변수에 모아둔 계산값을 양분에다 더해줍니다.

xxxxxxxxxx
void spring_summer()
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (arr[i][j].size!=-1)//나무들 존재한다면
            {
                int size = arr[i][j].size;
                sort(arr[i][j].tree, arr[i][j].tree + (size+1));//오름차순
​
                int dead_tree = 0;//죽은 나무들 모아둠 (나중에 양분에 더할 것)
​
                for (int s = 0; s <= size; s++)
                {
                    int tr = arr[i][j].tree[s];
​
                    if (arr[i][j].yummy >= tr) {
                        arr[i][j].yummy = arr[i][j].yummy - tr;
                        arr[i][j].tree[s] = tr + 1;
    
                    }
                    else {
                        dead_tree += tr / 2;
                        arr[i][j].tree[s] = NULL;
                        arr[i][j].size--;
                    }
                }
                arr[i][j].yummy += dead_tree;//죽은 나무들 양분에 더함
            }
        }
    }
}

 

• 가을

나무의 나이가 5의 배수라면 인접한 8칸에 나이가 1인 나무를 심어줄 수 있습니다. 이때, 배열의 범위를 벗어나지 않게 하는 것이 중요합니다.

xxxxxxxxxx
int dx[8] = { -1,1,0,0,-1,-1,1,1 };
int dy[8] = { 0,0,-1,1,-1,1,-1,1 };

현재 좌표에서 상하좌우 각 대각선 방향의 배열을 담아서 배열을 넘지 않으면 나이가 1인 나무를 추가하도록 했습니다.

xxxxxxxxxx
void fall()
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (arr[i][j].size != -1)//나무들 존재한다면
            {
                int size = arr[i][j].size;
                for (int s = 0; s <= size; s++)
                {
                    int data = arr[i][j].tree[s];
                    if (data % 5 == 0)//나무의 나이가 5의 배수라면
                    {
                        for (int d = 0; d < 8; d++) 
                            if (i + dx[d] > -1 && i + dx[d]<n && j + dy[d]>-1 && j + dy[d] < n) //범위를 넘지 않는 선에서
                                arr[i + dx[d]][j + dy[d]].tree[++(arr[i + dx[d]][j + dy[d]].size)] = 1;//추가해줌
                    }
                }
​
            }
        }
    }
}

 

• 겨울

겨울은 별거 없네용 ㅎㅎㅎ

봄, 여름 , 가을이 끝나고 입력받을 때 저장해둔 양분값으로 2차원 배열을 순회하며 양분값을 더해주면 됩니다.

 

---

Total

xxxxxxxxxx
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
using namespace std;
​
typedef struct {
    int tree[2000];
    int size = -1;
    int yummy = 5;
}TREE;
​
TREE arr[102][102];
​
int n, m, k;
int winterr[102][102];
​
void spring_summer()
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (arr[i][j].size!=-1)
            {
                int size = arr[i][j].size;
                sort(arr[i][j].tree, arr[i][j].tree + (size+1));
​
                int dead_tree = 0;
​
                for (int s = 0; s <= size; s++)
                {
                    int tr = arr[i][j].tree[s];
​
                    if (arr[i][j].yummy >= tr) {
                        arr[i][j].yummy = arr[i][j].yummy - tr;
                        arr[i][j].tree[s] = tr + 1;
    
                    }
                    else {
                        dead_tree += tr / 2;
                        arr[i][j].tree[s] = NULL;
                        arr[i][j].size--;
                    }
                }
                arr[i][j].yummy += dead_tree;
            }
        }
    }
}
​
int dx[8] = { -1,1,0,0,-1,-1,1,1 };
int dy[8] = { 0,0,-1,1,-1,1,-1,1 };
​
void fall()
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (arr[i][j].size != -1)
            {
                int size = arr[i][j].size;
                for (int s = 0; s <= size; s++)
                {
                    int data = arr[i][j].tree[s];
                    if (data % 5 == 0)
                    {
                        for (int d = 0; d < 8; d++) 
                            if (i + dx[d] > -1 && i + dx[d]<n && j + dy[d]>-1 && j + dy[d] < n) 
                                arr[i + dx[d]][j + dy[d]].tree[++(arr[i + dx[d]][j + dy[d]].size)] = 1;
                    }
                }
​
            }
        }
    }
}
​
void winter()
{
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            arr[i][j].yummy += winterr[i][j];
}
​
void Input()
{
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            scanf("%d", &winterr[i][j]);
​
    int x, y, age;
    for (int i = 0; i < m; i++)
    {
        scanf("%d %d %d", &x, &y, &age);
        arr[x - 1][y - 1].tree[++(arr[x-1][y-1].size)] = age;
    }
}
​
void Solve()
{
    Input();
    int year = 0;
    for (int i = 0; i < k; i++)
    {
        spring_summer();
        fall();
        winter();
​
        year++;
    }
​
}
​
int Answer()
{
    int cnt = 0;
​
    for(int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if(arr[i][j].size!=-1)
                cnt += arr[i][j].size + 1;
    return cnt;
}
​
int main()
{
    Solve();
    printf("%d \n", Answer());
}
​