[삼성SW테스트] 백준 16235번 - 나무 재테크 (시뮬레이션)

삼성 SW 역량테스트 기출 문제이다. (유형: 시뮬레이션)

https://www.acmicpc.net/problem/16235

16235번: 나무 재테크

봄 여름 가을 겨울 각 계절이 도래할때마다 규칙에 맞게 나무들이 자라거나 죽거나 번식하거나, 양분이 추가되거나 양분이 줄어들게된다. K 년 이후 땅에 남아있는 전체 나무의 수를 계산해야 하는 시뮬레이션 문제다.

어제 푼 아기상어 문제와 달리, 우선순위 조건이 나무의 나이 하나여서 굳이 우선순위 큐를 사용할 필요는 없었다. 게다가 우선순위 큐를 사용하지 않길 잘한것이, 다른 블로그 주인이 우선순위 큐로 풀었더니 시간 초과가 나서 실패했다고 했다. 문제의 요구조건이 실행시간 0.3초 (C++기준) 내에 정답을 내야해서 이 방법은 한계가 있다.

 

이 문제처럼 비교조건이 한 가지라면 굳이 우선순위 큐 알았다고 이걸 쓸게 아니라 <algorithm>의 sort 함수로 일반 벡터를 쓰는게 더 효율적인 것 같다.

 

또, 역시나 깨달은 것은 시뮬레이션 문제든 완전탐색 문제든 동적 계획법 문제든 문제이해가 가장 중요하다는 것이다. 코드 35번째 줄의 주석과 같이 나는 처음에 나무의 나이가 남아있는 양분보다 많을 경우 나무가 그걸 다 먹고 죽어버리는 것으로 이해해서 풀었으나 그게 아니라 나무는 그냥 죽어버리고 양분은 남게되는 것이었다. 이처럼 문제 이해는 시간 단축에도 엄청난 요구 조건이 되기 때문에, 앞으로도 더 꼼꼼히 문제를 파악하고 이해해야겠다.

 

그 밖에 문제의 구현측면에서 어려운 점은 크게 없었다. 백준기준 정답률이 20%인 이 문제가 그래도 잘 풀려서 기분이 좋다.

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
#define maxlen 11
struct dir{
    int dr, dc;
};
dir direction[8] = { { 0, 1 }, { 1, 0 }, { -1, 0 }, { 0, -1 }, { 1, 1 }, { -1, -1 }, { 1, -1 }, { -1, 1 } };
 
int year = 0, answer = 0;
int N, M, K;
vector<int> Trees[maxlen][maxlen];
int A[maxlen][maxlen]; // 매년 새로 추가되는 양분의 배열
int Nourish[maxlen][maxlen];
 
void Simulation(){
    while (1){        
        vector<int> Dead[maxlen][maxlen]; // 죽은 나무들 나이 저장 (순서 필요없음)
        // 봄
        for (int row = 1; row <= N; row++){
            for (int col = 1; col <= N; col++){
                if (Trees[row][col].size()){
                    sort(Trees[row][col].begin(), Trees[row][col].end());
                    int loop_cnt = Trees[row][col].size();
                    for (int i = 0; i < loop_cnt; i++){
                        // 아직 나이만큼 소비 할 수 있다면
                        if (Nourish[row][col] - Trees[row][col][i] >= 0){
                            Nourish[row][col] -= Trees[row][col][i];
                            Trees[row][col][i] += 1;
                        }
                        else{
                            // 만약 이 나무의 나이만큼 양분이 없는 경우
                            //Nourish[row][col] = 0; --> 잘못생각한 부분. 양분이 모자를경우 그대로 두어야 했다.
                            Dead[row][col].push_back(Trees[row][col][i]);
                            Trees[row][col].erase(Trees[row][col].begin() + i);
                            loop_cnt--;
                            i--;
                        }
                    }
                }
            }
        }
        // 여름 - Nourish 업데이트
        for (int row = 1; row <= N; row++){
            for (int col = 1; col <= N; col++){
                for (int i = 0; i < Dead[row][col].size(); i++){
                    Nourish[row][col] += (int)(Dead[row][col][i] / 2);
                }
                Dead[row][col].clear();
            }
        }
        // 가을
        for (int row = 1; row <= N; row++){
            for (int col = 1; col <= N; col++){
                for (int i = 0; i < Trees[row][col].size(); i++){
                    if (Trees[row][col][i] % 5 == 0){
                        for (int j = 0; j < 8; j++){
                            int n_r = row + direction[j].dr;
                            int n_c = col + direction[j].dc;
                            if (n_r >= 1 && n_r <= N && n_c >= 1 && n_c <= N){
                                Trees[n_r][n_c].push_back(1);
                            }
                        }
                    }
                }    
            }
        }
        // 겨울    
        for (int row = 1; row <= N; row++){
            for (int col = 1; col <= N; col++){
                Nourish[row][col] += A[row][col];
            }
        }
        if (++year == K){
            for (int row = 1; row <= N; row++){
                for (int col = 1; col <= N; col++){
                    answer += Trees[row][col].size();
                }
            }
            cout << answer << '\n';
            break;
        }
    }
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> N >> M >> K;
    // 1. 매년 추가되는 양분의 배열 입력
    for (int i = 1; i <= N; i++){
        for (int j = 1; j <= N; j++){
            cin >> A[i][j];
            Nourish[i][j] = 5;
        }
    }
    // 2. 심어진 나무 정보 입력 (행, 열, 나이)
    int row, col, age;
    for (int i = 1; i <= M; i++){
        cin >> row >> col >> age;
        Trees[row][col].push_back(age);
    }
    // 3. 시뮬레이션
    Simulation();
    return 0;
}