백준 16235번 - 나무 재테크

백준 16235번 - 나무 재테크

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

16235번: 나무 재테크

이 문제는 구현 문제인 것 같다.

처음에 문제를 읽고, 봄, 여름, 가을, 겨울을 각각 함수로 만들고 deque와 tuple을 사용해 코드를 짜 보았는데

당연히 시간초과..

이유는 아마 deque를 사용하고 체크하는 과정에서 tuple을 사용하면 deque의 장점인 인덱스 접근의 의미가 사라진다.

(tuple은 index로 접근이 불가.. tie 또는 get을 사용해야 된데요!!)

deque <tuple>을 사용하다 보니 전체를 체크하려면 deque에서 전체를 꺼냈다가 다시 전체를 집어넣는 방식..

예제가 잘 돌아가길래 채점해봤는데 시간 초과였다.

한 시간 넘게 고민하다가 결국 구글링을 통해 알아낸 건 죽은 나무를 처리할 때 i번째 나무가 죽었다면, i부터 남은

모든 나무들은 전부 죽게 된다.(나이가 어린 나무부터 영양분 먹으므로)

이 점을 생각해서 코드를 짜보았다. (나무도 vector를 사용한 인접 리스트로 바꿨다ㅎㅎ)

 

#include <iostream>
#include <queue>
#include <deque>
#include <algorithm>
#include <vector>
#include <cstring>
#include <tuple>
#pragma warning(disable:4996)
using namespace std;
int n, m, k;
int A[11][11];
int eat[11][11];
int dx[8] = { -1,-1,-1,0,0,1,1,1 };
int dy[8] = { -1,0,1,-1,1,-1,0,1 };
 
vector<int>tree[11][11];
deque<tuple<int, int, int>>dead;
 
int main() {
    int a, b, c;
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &A[i][j]);
            eat[i][j] = 5;
        }
    }
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d", &a, &b, &c);
        tree[a - 1][b - 1].push_back(c);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            sort(tree[i][j].begin(), tree[i][j].end());
        }
    }
    while (k--) {
        /*봄에는 나무가 자신의 나이만큼 양분을 먹고, 나이가 1 증가한다.각각의 나무는 나무가 있는 1×1 크기의 칸에 있는 양분만 먹을 수 있다.
        하나의 칸에 여러 개의 나무가 있다면, 나이가 어린 나무부터 양분을 먹는다.만약, 땅에 양분이 부족해 자신의 나이만큼 양분을 먹을 수
        없는 나무는 양분을 먹지 못하고 즉시 죽는다.*/
        int x, y, age;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                sort(tree[i][j].begin(), tree[i][j].end());
                for (int s = 0; s < tree[i][j].size(); s++) {
                    if (tree[i][j][s] <= eat[i][j]) {
                        eat[i][j] -= tree[i][j][s];
                        tree[i][j][s]++;
                    }
                    else {
                        for (int l = tree[i][j].size() - 1; l >= s; l--) {
                            dead.push_back(make_tuple(i, j, tree[i][j][l]));
                            tree[i][j].pop_back();
                        }
                    }
                }
            }
        }
        /*여름에는 봄에 죽은 나무가 양분으로 변하게 된다.각각의 죽은 나무마다 나이를 2로 나눈 값이 나무가 있던 칸에 양분으로 추가된다.
        소수점 아래는 버린다.*/
        while (!dead.empty()) {
            tie(x, y, age) = dead.front();
            dead.pop_front();
            eat[x][y] += age / 2;
        }
        /*가을에는 나무가 번식한다.번식하는 나무는 나이가 5의 배수이어야 하며, 인접한 8개의 칸에 나이가 1인 나무가 생긴다.
        어떤 칸(r, c)와 인접한 칸은(r - 1, c - 1), (r - 1, c), (r - 1, c + 1), (r, c - 1), (r, c + 1), (r + 1, c - 1), (r + 1, c),
        (r + 1, c + 1) 이다.상도의 땅을 벗어나는 칸에는 나무가 생기지 않는다.*/
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int s = 0; s < tree[i][j].size(); s++) {
                    if (tree[i][j][s] % 5 == 0) {
                        for (int p = 0; p < 8; p++) {
                            int nx = i + dx[p];
                            int ny = j + dy[p];
                            if (0 <= nx && nx < n && 0 <= ny && ny < n) tree[nx][ny].push_back(1);
                        }
                    }
                }
            }
        }
        /*겨울에는 S2D2가 땅을 돌아다니면서 땅에 양분을 추가한다.각 칸에 추가되는 양분의 양은 A[r][c]이고, 입력으로 주어진다.*/
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                eat[i][j] += A[i][j];
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ans += tree[i][j].size();
        }
    }
    printf("%d\n", ans);
}

시간제한이 0.3초라 최적화를 제대로 하지 않으면 시간 초과가 무조건 나서 정답률도 되게 낮은 듯하다

이런 유형의 문제가 제일 싫다