[ 백준 16235 ] 나무 재테크 (C++)

백준의 나무 재테크(16235) 문제이다.

[ 문제 바로가기 ]

삼성전자 S직군 역량테스트 기출문제이다.

[ 문제풀이 ]

1) 문제 자체는 어렵지 않은데, 가장 처음에 어떻게 접근해야 될지 고민을 많이 한 문제이다.

   맵을 일반적으로 int형으로 받으면 안될 것 같았다. 왜냐하면, 하나의 칸에 여러개의 나무가 동시에 있을 수 있기 때문이다.

   또한, 각 칸마다 양분이 존재하기 때문에, int형으로 받으면 관리가 힘들 것 같았다.

   따라서, 본인은 map을 Vector로 받았다.

   vector<int> MAP[MAX][MAX]

   저 Vector에는 각 칸에 존재하는 여러 나무들의 나이만 저장해주었다.

   각 칸에 존재하는 양분은 Energy[][] 라는 int형 2차원 배열을 만들어서 저장해주었다. 또한, 입력으로 주어지는 추가되는 양분은

   Insert_Energy[][]라는 2차원 배열을 또 하나 만들어서 저장해 주었다.

   정리해보고 문제풀이에 들어가보자.

   MAP[MAX][MAX] 에는 각 칸에 존재하는 나무들의 나이들이 저장되 있구나 !

   Energy[MAX][MAX] 에는 각 칸에 존재하는 양분의 값이 저장되 있구나 !

   Insert_Energy[MAX][MAX] 에는 각 칸에 매년마다 추가되는 양분의 값이 저장되어 있구나 !

   이제 봄/여름/가을/겨울 순서로 어떻게 구현할지 구체적으로 알아보자.

2) 봄(Spring) - 어린 나무부터 양분을 나무 나이만큼 먹고, 나이가 1증가한다. 양분을 먹지못하면 즉시 죽는다.

   - 봄을 구현할 때, 본인은 모든 좌표를 탐색하면서 나무가 존재하는 좌표들에 대해서(MAP[x][y]의 size가 0이 아닌 곳)

     먼저 정렬을 해 주었다. 왜냐하면, 어린 나무부터 양분을 먹어야 하기 때문에, 해당 좌표에 존재하는 나무들의 나이를

     오름차순으로 정렬해 주었다.

     이 후, 현재 좌표에 존재하는 양분이 양분을 먹으려는 나무의 나이보다 크거나 같다면, 양분을 나무의 나이만큼 빼주고,

     증가하는 나이를 임시적으로 Vector를 하나 더 만들어서 저장해주었다.

     - 갑자기 임시적인 Vector가 왜 나왔을까 ????

       예를 들어서, (1, 1)에 나이가 1, 2, 3인 3그루의 나무가 존재하고, 현재 (1, 1)에는 3만큼의 양분이 있다고 생각해보자.

       나이가 1인 나무가 양분을 먹고, 나이가 2가 되고, 양분은 2가 될 것이다.

       나이가 2인 나무가 양분을 먹고, 나이가 3이 되고, 양분은 0이 될 것이다. 이후, 나이가 3인 나무는 양분을 못먹게 된다.

       결과적으로 보자면 (1, 1)에는 나이가 2, 3인 2그루의 나무가 존재하게 된다.

       하지만, 현재 MAP[1][1] 에는 { 1, 2, 3 }이 존재한다. 따라서, 위에서 나온 { 2, 3 }을 임시적인 Vector에 저장해주고

       MAP[1][1].clear()를 이용해서, 비워버리고, { 2, 3 } 만 다시 넣어주었다.

     위의 내용이 봄에서 구현해야 할 내용이다.

 

    여름(Summer) - 봄에 죽은 나무들이, 자기의 나이 / 2 만큼의 양분을 자기가 있던 칸에 양분으로 추가된다.

    - 봄에 죽은 나무들의 정보를 알아둬야 한다. 즉, 봄을 구현하는 내용을 위에서 설명했지만, 저대로 끝내버리면 안된다.

      죽은 나무들에 대한 정보를 가져와줘야 하기 때문이다. 처음에는 Vector를 이용해서, 죽은 나무들의 나이만 따로 저장해

      주었었는데, 메모리초과를 받았다. 그래서 본인은 봄과 여름을 한번에 구현해 주었다.

      위의 봄 설명에는 죽은 나무들에 대한 처리는 설명이 되어 있지 않다. 현재 칸에 양분이 양분을 먹으려는 나무의 나이보다

      더 크거나 같은 경우만 설명을 했기 때문이다.

      반대로, 양분을 먹으려는 나무의 나이보다 양분이 더 적은 경우도 구현해줘야 한다.

      이 경우에는, 나무가 죽는 경우를 의미한다. 즉, 해당 좌표에 이 나무 나이의 / 2한 값이 양분으로 추가된다. 따라서, 본인은

      죽는 나무들의 나이의 /2 한 값을 모두 저장하는 변수를 하나 만들어주었다.(변수명 : Die_Tree_Energy)

      이 변수에는 죽는 나무들이 추가해주는 양분의 양을 모두 더해서 저장해 주었고, 가장 마지막에 해당 좌표에 추가해 주었다.

      ( 절대 죽는 나무가 나올 때 마다 추가해주면 안되고, 마지막에 추가해 주어야 한다 !)

    가을(Fall) - 나무의 나이가 5의 배수인 나무들 주변 8칸에 나이가 1인 나무를 번식한다.

    - 모든 좌표를 돌면서, 나무들의 나이를 판단해서, 5의 배수라면 주변 8칸에 추가해주면 된다. 이 부분은 어렵지 않으므로

      소스코드를 참고하자

   

    겨울(Winter) - 모든 칸에, 양분이 추가된다.

    - 우리는 입력받을때, 추가되는 양분의 값을 Insert_Energy[][] 라는 2차원 배열에 저장해 두었다.

      Energy[i][j] = Enerhy[i][j] + Insert_Energy[i][j] 로 양분을 추가해주면 끝 !

처음에 접근만 잘한다면 어렵지 않은 문제였다고 생각한다.

[ 소스코드 ]

#include<iostream>
#include<algorithm>
#include<vector>
 
#define endl "\n"
#define MAX 11
using namespace std;
 
int N, M, K;
int Energy[MAX][MAX];
int Insert_Energy[MAX][MAX];
 
vector<int> MAP[MAX][MAX];
 
int dx[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int dy[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
 
void Input()
{
    cin >> N >> M >> K;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            cin >> Insert_Energy[i][j];
            Energy[i][j] = 5;
        }
    }
    
    for (int i = 0; i < M; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        MAP[a][b].push_back(c);
    }
}
 
void SpringAndSummer()
{
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            if (MAP[i][j].size() == 0) continue;
            
            int Die_Tree_Energy = 0;
            vector<int> Temp;
 
            sort(MAP[i][j].begin(), MAP[i][j].end());
            for (int k = 0; k < MAP[i][j].size(); k++)
            {
                int Age = MAP[i][j][k];
 
                if (Energy[i][j] >= Age)
                {
                    Energy[i][j] = Energy[i][j] - Age;
                    Temp.push_back(Age + 1);
                }
                else
                {
                    Die_Tree_Energy = Die_Tree_Energy + (Age / 2);
                }
            }
 
            MAP[i][j].clear();
            for (int k = 0; k < Temp.size(); k++)
            {
                MAP[i][j].push_back(Temp[k]);
            }
            Energy[i][j] = Energy[i][j] + Die_Tree_Energy;
        }
    }    
}
 
void Fall()
{
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            if (MAP[i][j].size() == 0) continue;
 
            for (int k = 0; k < MAP[i][j].size(); k++)
            {
                int Age = MAP[i][j][k];
 
                if (Age % 5 == 0)
                {
                    for (int a = 0; a < 8; a++)
                    {
                        int nx = i + dx[a];
                        int ny = j + dy[a];
 
                        if (nx >= 1 && ny >= 1 && nx <= N && ny <= N)
                        {
                            MAP[nx][ny].push_back(1);
                        }
                    }
                }
            }
        }
    }
}
 
void Winter()
{
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            Energy[i][j] = Energy[i][j] + Insert_Energy[i][j];
        }
    }
}
 
void Solution()
{
    for (int i = 0; i < K; i++)
    {
        SpringAndSummer();
        Fall();
        Winter();
    }
 
    int Answer = 0;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            Answer = Answer + MAP[i][j].size();
        }
    }
 
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}