백준(BOJ) 16235 - 나무 재테크

시뮬레이션 문제였다.

작년 하반기에 삼성 시험에서 이 문제를 풀때 스택을 사용하면, 최근에 추가한 나무가 가장 나이가 어리기 때문에 이 방법을 이용하여 넣었다 뺐다 하다가 시간초과가 났던 것이 기억났다.

이번에도 스택을 이용해서 풀자고 생각해서, 스택을 이용해서 깔끔하게 푼것 같았다. 예제케이스도 나와서 정말 깔끔하군! 생각했는데, AC를 받지 못했다.

스택을 사용하면 가장 어린놈을 순서대로 빼낼수 있다는 옜날 생각을 그대로 적용했던 것이 실수였다. 다시 생각해보니 시험당시에는 어린 순서를 맞춰주기 위해 스택하나를 더 두고 빼면서 임시스택에 넣고 결과값을 다시 스택에 저장하는 방법을 사용했다. 이 생각을 잊은채 걍 스택쓰면 되긴 했었는데? 라는 생각으로 스택을 썼고 계속 왜틀렸지만 반복했다.

이러니 그때 시간초과가 났지...

나이가 어린순을 유지하기위해 덱 자료구조를 이용했다.

가을에 추가되는 나무들은 push_back 으로 덱에 저장하고, 봄에 양분을 먹고 한살 더 자라날때에는 push_front로 앞에 추가해주어 나이 순서를 유지시켜주었다.

덱 자료구조를 tree[11][11][1001] 만큼 선언했는데, 사실 tree[11][11][2] 면 충분하다.

k를 %2연산하여 공간을 활용할 수 있지만 귀찮아서... 걍 했다.

tree변수에는 각 지역에 해당하는 나무들의 나이가 저장되어있다.

provide에는 입력으로 주어지는 겨울에 공급되는 양분의 양이 저장되어있다.

die[11][11] 에는 봄에 죽은나무 나이 /2 한값을 저장해 놨다가 여름에 더해준다.

fall[11][11]은 봄에 나이를 한살 먹고 5의 배수가 되는 나무들의 수가 저장되고, 가을에 이 수만큼 한살짜리 나무들을 주변에 추가해준다.

덱을 사용하니 200ms이 나왔다. 삼성은 통과할 수준이지만, 많이 느린 방법이다. 

정답을보니 갓님들의 풀이가 많이 보였다. 시간날때 하나씩 봐야겠다.

#include <iostream>
#include <cstdio>
#include <deque>
 
using namespace std;
int N, M, K;
int provide[11][11];
int map[11][11];
 
deque<int> tree[11][11][1001];
int die[11][11];
int fall[11][11];
int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
 
 
int main(void){
   scanf("%d %d %d", &N, &M, &K);
 
   for(int i = 1; i <= N; i++){
       for(int j = 1 ; j <= N; j++){
            scanf("%d", provide[i] + j);
            map[i][j] = 5;
       }
   }
 
   for(int i = 0 ; i < M; i++){
        int r, c, a;
        scanf("%d %d %d", &r, &c, &a);
        tree[r][c][0].push_front(a);
   }
 
 
   for(int k = 0 ; k < K; k++){
       for(int i = 1; i <= N; i++){
           for(int j = 1 ; j <= N; j++){
                while(!tree[i][j][k].empty()){
                    int age = tree[i][j][k].back();
                    tree[i][j][k].pop_back();
                    if(age <= map[i][j]){
                        map[i][j] -= age;
                        tree[i][j][k+1].push_front(age + 1);
 
                        if((age + 1) % 5 == 0){
                            fall[i][j]++;
                        }
 
                    }
                    else{
                        die[i][j] += age/2;
                    }
                }
 
 
           }
       }
       for(int i = 1 ; i <= N; i++){
           for(int j = 1 ; j <= N; j++){
               map[i][j] += die[i][j];
               die[i][j] = 0;
               for(int l = 0; l < fall[i][j]; l++){
                   for(int m = 0; m < 8; m++){
                       int ni = i + dy[m];
                       int nj = j + dx[m];
                       if(ni > 0 && ni <= N && nj > 0 && nj <= N ){
                            tree[ni][nj][k + 1].push_back(1);
                       }
                   }
               }
               fall[i][j] = 0;
 
               map[i][j] += provide[i][j];
           }
       }
 
 
   }
   int cnt = 0 ;
   for(int i = 1 ; i <= N; i++){
       for(int j = 1 ; j <= N; j++){
           cnt += tree[i][j][K].size();
       }
   }
    printf("%d\n", cnt);
 
 
}