[백준 16235번] 나무 재테크

문제 링크: https://www.acmicpc.net/problem/16235

16235번: 나무 재테크

<문제 풀이> 구현, 시뮬레이션, 자료구조, deque(덱)

 

문제에서 요구하는 것을 그대로 구현하면 되는데 몇 가지 주의할 점이 있습니다.

 

1. 가장 처음에 양분은 모든 칸에 5만큼 들어있다.

처음에 양분을 초기화할 때 5로 초기화해야 합니다. A[r][c]로 초기화하면 안 됩니다.

 

2. 죽은 나무마다 나이를 2로 나눈 값이 나무가 있던 칸에 양분으로 추가된다.

 

이 요구사항을 구현할 때 죽은 나무의 나이를 모두 합해서 2로 나누면 안 됩니다.

 

죽은 나무마다 나이를 2로 나눈 값을 구한 뒤 모두 합해야합니다.

 

예를 들어

 

죽은 나무의 나이가 각각 7, 9, 11이라고 했을 때 추가될 양분의 양을 구해보면  아래와 같습니다.
7/2 + 9/2 + 11/2 

위 수식을 다음과 같이 쓸 수 있습니다.

(7 + 9 + 11) / 2

그러나 위 두 식이 동치일지라도 실제로 구하는 값은 소수점을 버리기 때문에 같은 값이 나오지 않습니다.

 

7/2 + 9/2 + 11/2 == 12

(7 + 9 + 11) / 2 == 13

 

따라서 죽은 나무마다 나이를 2로 나눈 값을 구한 뒤 모두 합해야 합니다.

 

3. 나이가 어린 나무부터 양분 먹이기, 나이가 1인 나무 생성 구현 시 매 순간 정렬할 필요가 없다.

deque(덱) 자료구조를 사용하면 매 순간 정렬할 필요가 없습니다.

나이가 1인 나무를 생성할 때는 deque의 맨 앞에 삽입하고,

나머지는 deque의 맨 뒤에 삽입하면 됩니다.

 

문제의 제한 조건에서 입력으로 주어지는 나무의 위치는 모두 서로 다르다고 했습니다.

 

따라서 초기에 덱에 삽입된 나이들은 오름차순으로 정렬된 상태입니다.

 

나이가 1인 나무를 생성할 때 deque의 맨 앞에 계속 삽입하면 자연스럽게 오름차순 정렬이 유지가 됩니다.

(1보다 작은 나이는 없기 때문)

 

나이를 증가시킬 때는 오름차순으로 정렬되어 있는 deque를 순회하면서 양분을 먹고 나이가 증가할 수 있는 상태이면, deque의 맨 뒤에 삽입하면 됩니다.

(deque는 오름차순으로 정렬되어 있고, 나이는 무조건 1씩 증가하기 때문에 나중에 나온 나이는 이전에 나온 나이보다 항상 크거나 같다.)

 

 

 

<C++소스코드>

#include <iostream>
#include <queue>
#include <vector>
#include <deque>
using namespace std;
 
int n, m, k;
 
int A[11][11];
int nutrients[11][11];
int dead[11][11];
deque<int> board[11][11];
int const dx[8] = {0, 0, 1, -1, 1, 1, -1, -1};
int const dy[8] = {1, -1, 0, 0, 1, -1, 1, -1};
 
 
 
void spring() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            deque<int> temp; //양분을 먹고 나이가 증가한 나무들만 저장하기 위한 임시 변수
            int size = board[i][j].size();
            for(int k=0; k<size; k++){
                int age = board[i][j][k];
                if (nutrients[i][j] < age) {//양분이 부족하면 죽는다.
                    dead[i][j] += age/2;
                }
                else {// 자신의 나이만큼 양분을 먹고 나이가 1증가한다.
                    nutrients[i][j] -= age;
                    temp.push_back(age + 1); 
                }
            }
            board[i][j] = temp;
        }
    }
}
 
void summer() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (dead[i][j]) { // 만약 죽은 나무가 존재하면
                nutrients[i][j] += dead[i][j]; // 죽은 나무들의 나이를 2로 나눈 값이 양분으로 추가된다.
                dead[i][j] = 0;
            }
        }
    }
}
 
void fall() {
    deque<int> temp[11][11];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int size = board[i][j].size();
            for (int k = 0; k < size; k++) {
                int age = board[i][j][k];
                if (age % 5 == 0) { // 번식하는 나무는 나이가 5의 배수
                    for (int dir = 0; dir < 8; dir++) {
                        int nx = i + dx[dir];
                        int ny = j + dy[dir];
                        if (nx < 1 || ny < 1 || nx >n || ny > n)continue;
                        temp[nx][ny].push_front(1); //1을 앞에 삽입하면 정렬 상태가 유지
                    }
                }
                temp[i][j].push_back(age); //나이는 오름차순으로 되어 있음
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            board[i][j] = temp[i][j];
        }
    }
}
 
void winter() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            nutrients[i][j] += A[i][j]; // 각 칸에 양분을 추가한다;
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> A[i][j];
            nutrients[i][j] = 5; // 처음 모든 양분은 5만큼 들어있다.
        }
    }
    for (int i = 0; i < m; i++) {
        int x, y, z; cin >> x >> y >> z;
        board[x][y].push_back(z);
    }
    while (k--) {
        spring();
        summer();
        fall();
        winter();
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cnt += board[i][j].size();
        }
    }
    cout << cnt;
 
    return 0;
 
}