[BOJ] 백준 16235 나무 재테크 (C++)

삼성 SW 코딩 테스트 준비(A형)

삼성 SW 기출 모음

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

 Input 

5 2 2

2 3 2 3 2

2 3 2 3 2

2 3 2 3 2

2 3 2 3 2

2 3 2 3 2

2 1 3

3 2 3

　 

 Output 

15　

어떤 언어와 자료구조를 이용하느냐에 따라 구현 차이가 있을 수 있습니다.

- 한 칸에 여러 나무가 존재

- 봄에 양분을 먹는 경우 나이가 어린 나무부터 양분을 먹는다.

- 양분을 죽지 못한 나무는 죽으면서 해당 칸의 양분으로 더해집니다.

- map[][] 안에 양분energy과 나무 목록 tList를 가집니다.

    - [봄]: 나이가 작은 순으로 양분을 먹기 위해서 sort() 처리

    - [여름]: 죽은 나무를 리스트에서 pop하기 위해서 살아남은 나무를 따로 저장해서 리스트를 교체합니다.

    - [가을]: 살아남은 나무 중 나이가 5의 배수에 해당하는 경우 8가지 방향에 나무를 심습니다.

    - [겨울]: 각 칸의 양분map[i][j].enery에 A[i][j] 수치를 더해줍니다.

 

※ [Java 버전]

[BOJ] 백준 16235 나무 재테크 (Java)

---

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int dx[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
const int dy[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
const int MAX_N = 10 + 2;
int N, M, K, ans;
int A[MAX_N][MAX_N];
 
struct Map {
    int energy;
    vector<int> tList;
    void push(int age) { tList.push_back(age); }
    int size() { return tList.size(); }
    void treeSort() { sort(tList.begin(), tList.end()); }
    void clear() { tList.clear(); }
}map[MAX_N][MAX_N];
 
void SpringSummer(){
    for (int x = 1; x <= N; x++){
        for (int y = 1; y <= N; y++){
            if (map[x][y].size() == 0) continue;
 
            int plusEnergy = 0;
            map[x][y].treeSort();
            vector<int> survivalTree;
            for (int k = 0; k < map[x][y].size(); k++){
                int age = map[x][y].tList[k];
                // 양분이 충분한 경우
                if (map[x][y].energy >= age) {
                    map[x][y].energy -= age;
                    survivalTree.push_back(age + 1);
                    continue;
                }
                
                // 양분이 부족한 경우
                // {해당 나무 나이 / 2}를 양분에 더해줍니다.
                plusEnergy += (age / 2);
            }
 
            // 여름
            // 살아남은 나무만 해당 칸에 저장해주고, 죽은 나무는 양분으로 처리
            map[x][y].clear();
            for (int k = 0; k < survivalTree.size(); k++){
                map[x][y].push(survivalTree[k]);
            }
            map[x][y].energy += plusEnergy;
        }
    }
}
 
void FallWinter(){
    // 가을
    for (int x = 1; x <= N; x++){
        for (int y = 1; y <= N; y++){
            if (map[x][y].size() == 0) continue;
 
            for (int k = 0; k < map[x][y].size(); k++){
                int age = map[x][y].tList[k];
 
                if (age % 5 == 0){ // 나이가 5의 배수인 경우
                    for (int dir = 0; dir < 8; dir++){
                        int nextX = x + dx[dir];
                        int nextY = y + dy[dir];
                        if (nextX < 1 || nextY < 1 || nextX > N || nextY > N)
                            continue;
                        map[nextX][nextY].push(1);
                    }
                }
            }
        }
    }
 
    // 겨울
    for (int x = 1; x <= N; x++) {
        for (int y = 1; y <= N; y++) {
            map[x][y].energy += A[x][y];
        }
    }
}
 
int main(void){
    // freopen("Input.txt", "r", stdin);
    scanf("%d %d %d", &N, &M, &K);
    for (int x = 1; x <= N; x++) {
        for (int y = 1; y <= N; y++) {
            scanf("%d", &A[x][y]);
            map[x][y].energy = 5;
        }
    }
 
    int x, y, age;
    for (int i = 0; i < M; i++) {
        scanf("%d %d %d", &x, &y, &age);
        map[x][y].push(age);
    }
 
    while (K--) {
        SpringSummer();
        FallWinter();
    }
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            ans += map[i][j].size();
        }
    }
    printf("%d\n", ans);
}