16235번 : 나무 재테크

근래 출제된 삼성 문제의 특징 중 하나는, 대단한 알고리즘을 요구하는 것보다도

 

독해력을 많이 보는 것이 아닐까 한다.

 

아기상어는 std::priority_queue가 사용가능하다면 금방 풀수 있고

나무재테크는 알고리즘이랄게 아예 없다.

 

다만 둘다 문장 하나하나에 조건이 조그마하게 숨어있어서 처음 문제 파악할 떄

제대로 읽지않는다면 낭패를 보거나 풀이 자체가 불가능하다.

 

예를 들어, 나무재테크 문제는 이동방향이 대각선 포함 8방향이다.

처음에 문제를 제대로 안읽으면 4방향이라 어림짐작하고 덤비기 쉽상이다.

 

일단 돌아와서 문제의 포인트는 정렬, 그리고 문제를 봄,여름,가을,겨울에서 봄+여름,가을,겨울 로 나눠 생각하는거다.

또 최초영양분이 모든칸에서 5라는 사실을 잊어선 안된다.

 

죽음과 삶이란 상태가 있는것 처럼 보이지만 그렇지 않다.

사실상 봄에 나이먹는과정+양분 부족해서 시체로 만드는과정을 합친게 한 칸에서 한번에 이루어지기 떄문이다.

자료구조는 vector들의 2차원배열 vector<int> land[11][11]->  land[r][c]->(r,c)는 나무 나이 벡터로 충분해보인다.

 

그러므로 봄이 시작하기전에

1. 나이순으로 정렬을 하고

2. 나이를 먹이면서 영양을 빼고(나이먹은 나무는 따로 aging벡터에 저장한다)

3. 영양이 부족하면 나이/2를 시체로 만든다.

4. 백업해둔 aging벡터로 기존 나이를  덮는다.

 

가을 겨울은 너무 쉬워서 패스. 

 

시간초과가 많이난다는 평이 있는데, 개인적으론 시뮬레이션 문제는 정말 특이한 경우가 아니면  C++로 푸는게 좋다고 본다.

Python list 만큼은 아니지만 STL만 해도 알고리즘구현하는데 충분한 유연성을 제공해줄수있고,

로직이 다소 개판이어도 빠른 성능으로 커버할 수 있다.

 

 

 

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> land[11][11];
int F[11][11];
int A[11][11];
int N, M, K;
int dr[] = { -1,    -1,    -1,    0,    0,    1,    1,    1 };
int dc[] = { -1,     0,     1,    1,    -1,    -1,    0,    1 };
 
void first_half()
{
    for (int r = 1; r <= N; r++)
    {
        for (int c = 1; c <= N; c++)
        {
            vector<int> aging;
            sort(land[r][c].begin(), land[r][c].end());
            int dead = 0;
            for (size_t i = 0; i < land[r][c].size(); i++)
            {
                if (land[r][c][i] <= F[r][c])
                {
                    F[r][c] -= land[r][c][i];
                    aging.push_back(land[r][c][i] + 1);
                }
                else
                {
                    dead += land[r][c][i] / 2;
                }
            }
            // 산 나무
            land[r][c].clear();
            for (size_t i = 0; i < aging.size(); i++)
            {
                land[r][c].push_back(aging[i]);
            }
            F[r][c] += dead;
        }
    }
}
 
void second_half()
{
    for (int r = 1; r <= N; r++)
    {
        for (int c = 1; c <= N; c++)
        {
            for (int i = 0; i < land[r][c].size(); i++)
            {
                if (land[r][c][i] % 5) continue;
                int nr, nc;
                for (int d = 0; d < 8; d++)
                {
                    nr = r + dr[d];
                    nc = c + dc[d];
                    if (nr > 0 && nr <= N && nc > 0 && nc <= N)
                    {
                        land[nr][nc].push_back(1);
                    }
                }
            }
        }
    }
    for (int r = 1; r <= N; r++)
    {
        for (int c = 1; c <= N; c++)
        {
            F[r][c] += A[r][c];
        }
    }
}
int main(void)
{
    cin >> N >> M >> K;
    for (int r = 1; r <= N; r++)
        for (int c = 1; c <= N; c++)
        {
            cin >> A[r][c];
            F[r][c] = 5;
        }
    int r, c, a;
    for (int i = 1; i <= M; i++)
    {
        cin >> r >> c >> a;
        land[r][c].push_back(a);
    }
    for (int k = 0; k < K; k++)
    {
        first_half();
        second_half();
    }
    int trees = 0;
    for (int r = 1; r <= N; r++)
        for (int c = 1; c <= N; c++)
            trees += land[r][c].size();
    cout << trees << '\n';
    return 0;
}