문제

k 년이 지난 후 살아남은 나무의 개수를 구하는 문제

1. n 격자의 크기 (1 <= n <= 10)

2. m 나무의 개수 (1 <= m <= n^2)

3. k 년수 ( 1 <= k <= 1000)

4. 제일 처음 모든 칸의 양분은 5 입니다.

5. 봄
   나무가 자신의 나이만큼 양분을 먹고 나이가 1 증가 합니다.
   양분은 1*1 칸에 있는 양분만 먹을 수 있습니다.
   하나의 칸에 여러 나무가 있으면 어린 나무 부터 먹습니다.
   양분이 부족하면 나무는 즉시 죽습니다.

6. 여름
   봄에 죽은 나무가 양분이 됩니다.
   (죽은 나무 나이 / 2 ) 에 해당하는 값이 양분으로 추가됩니다. 소수점이하는 버립니다.

7. 가을
   나무가 번식합니다.
   번식하는 나무는 나이가 5의 배수 입니다.
   인접한 8칸에 나이 1인 나무가 생깁니다.

8. 겨울
   S2D2가 양분을 추가합니다. 양분의 양은 a[r][c]입니다.
   

• 시간 제한 0.3초
• 문제 링크

---

풀이 과정

0. 요약

이번 문제는 시뮬레이션 문제로 특별한 알고리즘을 사용하지 않습니다. 주어진 문제를 잘 읽고 정리해서 구현할 수 있어야했습니다.

다만, 조금 더 중요했던 부분은 '시간 초과'

죽은 나무 를 제거 하는 것이 중요했습니다.

1. 문제 소감

저는 인접리스트와 sort를 썼는데,

정렬안하고 더 빨리 할 수 있을거 같기는 한데 음 내일 알아볼래요.

코드

1. C++

#include <iostream>
#include <vector>
#include <algorithm>
#define max_int 11
#define max_val 1001

using namespace std;

int n, m, k, ground[max_int][max_int], a[max_int][max_int], dead[max_int][max_int], x, y, z, result;
int dx[] = {0, 0, 1, -1, -1, -1, 1, 1}, dy[] = {-1, 1, 0, 0, -1, 1, 1, -1};


vector<int> v[max_int][max_int];

int main(){
    // 1. 입력, n 격자의 크기, m 나무의 개수, k 년수
    scanf("%d %d %d", &n, &m, &k);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            // 각 칸의 양분을 입력받습니다.
            scanf("%d", &a[i][j]);
            // 초기 양분은 5로 초기화
            ground[i][j] = 5;
        }
    }
    
    // m 개의 나무 정보를 받습니다.
    for(int i=1; i<=m; i++){
        scanf("%d %d %d", &x, &y, &z);
        v[x][y].push_back(z);
        result++;
    }
    
    // 2. k년 동안 반복합니다.
    for(int year=1; year<=k; year++){
        
        // 초기화
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                // 나이가 어린 나무부터 먹을 수 있도록 정렬
                sort(v[i][j].begin(), v[i][j].end());
                //죽은 나무의 양분을 더해줍니다.
                ground[i][j] += dead[i][j];
                // 양분을 더했으면 초기화해줍니다.
                dead[i][j] = 0;
            }
        }
        
        // 봄, 여름
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                for(int k=0; k<(int)v[i][j].size(); k++){
                    // 남은 양분이 나이보다 클때
                    if(ground[i][j] >= v[i][j][k]){
                        ground[i][j] -= v[i][j][k];
                        v[i][j][k] += 1;
                    }
                    // 남은 양분이 나이보다 작을때
                    else{
                        
                        int idx = k;
                        int size = (int)v[i][j].size();
                        
                        // 죽은 나무 인접 리스트에서 제거
                        for(int l=size-1; l>=idx; l--){
                            dead[i][j]+= (v[i][j][l] / 2);
                            v[i][j].pop_back();
                            result--;
                        }
                        break;
                    }
                }
            }
        }
        
        
        // 가을
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                for(int s=0; s<v[i][j].size(); s++){
                    int tree = v[i][j][s];
                    // 나무의 나이가 5의 배수일때
                    if(tree % 5 != 0) continue;
                    
                    // 인접한 8칸에 나이 1인 나무를 번식합니다.
                    for(int k=0; k<8; k++){
                        int nx = i + dx[k];
                        int ny = j + dy[k];
                        
                        if(nx > n || nx < 1 || ny > n || ny < 1) continue;
                        
                        v[nx][ny].push_back(1);
                        result++;
                    }
                }
            }
        }
        
        // 겨울
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                // S2D2 기계가 양분을 더해줍니다.
                ground[i][j] += a[i][j];
            }
        }
    }
    
    // 3. 출력
    printf("%d\n", result);
}