[BOJ][C++] 16235 나무재테크

[BOJ][C++] 16235 나무재테크

 

문제

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

 

풀이

시간초과 때문에 몇 번을 다시 풀었던 문제 입니다. 문제 풀면서 시간 고려도 하는 버릇을 길러야겠어요

2차원 배열에 벡터 형태로 나무를 쌓는 식(z축)으로 했습니다.

그리고 k년만큼 for문을 돌면서 봄, 여름, 가을, 겨울 을 순으로 코드를 짰어요.

 

봄 >

봄은 나이만큼 양분을 먹노 나이가 증가합니다. 나이만큼 양분이 없는 경우 여름에 비료로 쓸 수 있도록 dead배열을 하나 더 만들어 나이/2를 한 값을 저장해줍니다. 주의할 것은 나이가 어린 순 부터 비료를 쓸 수 있기에 sort를 해주었습니다.

여름 >

저장해 놓았던 dead배열의 값을 더해줍니다. 이 때, dead배열 초기화를 해줍니다.

가을 >

dx, dy 배열을 만들어 여덟 방향을 갈 수 있도록 해줍니다. 주의해야 할 것은 age배열에 나무를 추가해 심을 경우 나무의 수가 계속 변해서 오류가 날 수 있어요. 그렇기 때문에 임시 배열 하나를 만들어 복사해준 뒤 임시 배열에 나무를 심어줍니다. 5의 배수 나이를 갖고 있는 나무 주위로 모든 나무를 심어주고 나면 심은 나무를 다시 원본 배열에 복사해줍니다. 

겨울>

p_compost배열에 저장해놨던 값을 compost배열에 더해줍니다.

 

k년 만큼 모두 돌면 age[i][j]에 있는 나무들의 size를 측정해서 다 더해주면 됩니다.

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;


int main() {
    int n, m, k;
    int p_compost[11][11];
    vector<int> age[11][11];
    int compost[11][11];
    int dead_tree[11][11];
    int dx[] = { 1,-1,0,0,1,-1,1,-1 };
    int dy[] = { 0,0,1,-1,1,-1,-1,1 };

    scanf("%d %d %d", &n, &m, &k);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &p_compost[i][j]);
            compost[i][j] = 5;
        }
    }

    //나무 입력받기
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        age[x][y].push_back(z);

    }
    //년도 증가
    for (int i = 0; i < k; i++) {
        //1.봄
        for (int p = 1; p <= n; p++) {
            for (int q = 1; q <= n; q++) {
                if (!age[p][q].empty()) {
                    sort(age[p][q].begin(), age[p][q].end());
                    for (int j = 0; j < age[p][q].size(); j++) {
                        if (compost[p][q] >= age[p][q][j]) {
                            compost[p][q] -= age[p][q][j];
                            age[p][q][j]++;
                        }
                        else {
                            dead_tree[p][q] += age[p][q][j] / 2;
                            age[p][q].erase(age[p][q].begin() + j);
                            j--;
                        }
                    }
                }
            }
        }

        //2.여름
        for (int p = 1; p <= n; p++) {
            for (int q = 1; q <= n; q++) {
                compost[p][q] += dead_tree[p][q];
            }
        }
        for (int p = 1; p <= n; p++) {
            for (int q = 1; q <= n; q++) {
                dead_tree[p][q] = 0;
            }
        }
        //3.가을
        vector<int> tmp[11][11];
        for (int p = 1; p <= n; p++) {
            for (int q = 1; q <= n; q++) {
                for (int j = 0; j < age[p][q].size(); j++) {
                    tmp[p][q].push_back(age[p][q][j]);
                }
            }
        }
        for (int p = 1; p <= n; p++) {
            for (int q = 1; q <= n; q++) {
                for (int j = 0; j < age[p][q].size(); j++) {
                    if (age[p][q][j] % 5 == 0) {
                        for (int l = 0; l < 8; l++) {
                            int nx = p + dx[l];
                            int ny = q + dy[l];
                            if (nx <= 0 || ny <= 0 || nx > n || ny > n) continue;
                            tmp[nx][ny].push_back(1);
                        }
                    }
                }
            }
        }
        for (int p = 1; p <= n; p++) {
            for (int q = 1; q <= n; q++) {
                age[p][q].clear();
                for (int j = 0; j < tmp[p][q].size(); j++) {
                    age[p][q].push_back(tmp[p][q][j]);
                }
            }
        }

        //4.겨울
        for (int p = 1; p <= n; p++) {
            for (int q = 1; q <= n; q++) {
                compost[p][q] += p_compost[p][q];
            }
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            res += age[i][j].size();
        }
    }
    printf("%d\n", res);
}