16235 c++ - 나무 재테크

나무는 (x, y)라고 해놓고선 r,c로 들어왔다. 문제가 날 속임. (그래서 틀림...ㅠㅠ)

결국 맞췄을땐 vector로하면 시간초과가 난다는 것을 알게 되었다.
처음에 문제 잘 읽고 시간 제한 보긴했지만 구현 문제라서 그냥 주어진 상황대로 풀었다. 

둘을 비교했을때, 나무의 수가 커지면 커질수록 더 차이가 난다.

# Let's calculate the complexity of both versions of the code to compare their potential performance.

# Old Version (using vector<Tree>):
# In the old version, we have:
# - Spring: Sorting the entire vector<Tree> by age each spring, which is O(M log M), where M is the number of trees.
# - Summer: Traversing through all trees, which is O(M).
# - Autumn: For every tree, we check if it can reproduce and spawn new trees in 8 directions, which is O(8M) ~ O(M).
# - Winter: We add nutrients to every cell, which is O(N^2).

# Overall complexity: O(K * (M log M + M + M + N^2)) = O(K * (M log M + N^2)) for K years.

# Optimized Version (using deque<int> per cell):
# - Spring and Summer: We traverse each deque in every cell and update the age of trees or remove dead ones. The time complexity per cell is proportional to the number of trees in that cell.
# - Autumn: Same reproduction, O(M), but deque operations are faster than vector insertions.
# - Winter: Same, O(N^2).

# In this case, the complexity per year is O(N^2 * T), where T is the average number of trees per cell.

# Let's assume the following parameters for testing:
# M = 100 (number of trees), N = 10 (size of land), K = 1000 (years).
# We'll compare the estimated time complexity for both versions.

import math

def old_version_complexity(M, N, K):
    return K * (M * math.log2(M) + M + N**2)

def optimized_version_complexity(M, N, K):
    return K * (N**2 * M // (N**2))

# Let's compare for M = 100, N = 10, K = 1000
M = 100
N = 10
K = 1000

old_version = old_version_complexity(M, N, K)
optimized_version = optimized_version_complexity(M, N, K)

old_version, optimized_version
결과
(864385.6189774724, 100000)

vector 풀이.

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

struct Tree {
  int r, c, age;
  bool die;
};
vector<Tree> trees;
vector<vector<int>> land;
vector<vector<int>> a;

int n, m, k;
int dx[] = {1, 1, 1, 0, 0, -1, -1, -1};
int dy[] = {1, 0, -1, 1, -1, 1, 0, -1};

bool compareAge(Tree a, Tree b) { return a.age < b.age; }

void spring() {
  sort(trees.begin(), trees.end(), compareAge);
  for (auto &t : trees) {
    if (land[t.r][t.c] - t.age < 0) {
      t.die = true;
    } else {
      land[t.r][t.c] -= t.age;
      t.age++;
    }
  }
}

void summer() {
  vector<Tree> newTrees;
  for (auto &t : trees) {
    if (t.die) {
      land[t.r][t.c] += (t.age / 2);
    } else {
      newTrees.push_back(t);
    }
  }
  trees.clear();
  trees = newTrees;
}

void autumn() {
  vector<Tree> newTrees;
  for (auto &t : trees) {
    if (t.age % 5 != 0) continue;
    for (int i = 0; i < 8; i++) {
      int ny = dy[i] + t.r;
      int nx = dx[i] + t.c;

      if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
      newTrees.push_back({ny, nx, 1, false});
    }
  }
  trees.insert(trees.end(), newTrees.begin(), newTrees.end());
}

void winter() {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      land[i][j] += a[i][j];
    }
  }
}

int main() {
  cin >> n >> m >> k;
  land.resize(n, vector<int>(n, 5));
  a.resize(n, vector<int>(n, 0));

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> a[i][j];
    }
  }

  for (int i = 0; i < m; i++) {
    int tr, tc, tage;
    cin >> tr >> tc >> tage;
    trees.push_back({tr - 1, tc - 1, tage, false});
  }

  while (k--) {
    spring();
    summer();
    autumn();
    winter();
  }

  cout << trees.size();

  return 0;
}

 

deque 풀이.

/* ************************************************************************** */
/*                                                                            */
/*                                                      :::    :::    :::     */
/*   Problem Number: 16235                             :+:    :+:      :+:    */
/*                                                    +:+    +:+        +:+   */
/*   By: chanhihi <boj.kr/u/chanhihi>                +#+    +#+          +#+  */
/*                                                  +#+      +#+        +#+   */
/*   https://boj.kr/16235                          #+#        #+#      #+#    */
/*   Solved: 2024/10/08 15:33:53 by chanhihi      ###          ###   ##.kr    */
/*                                                                            */
/* ************************************************************************** */
#include <algorithm>
#include <deque>
#include <iostream>
#include <vector>

using namespace std;

struct Tree {
  int r, c, age;
  bool die;
};

vector<vector<deque<int>>> trees;
vector<vector<int>> land;
vector<vector<int>> a;

int n, m, k;
int dx[] = {1, 1, 1, 0, 0, -1, -1, -1};
int dy[] = {1, 0, -1, 1, -1, 1, 0, -1};

bool compareAge(Tree a, Tree b) { return a.age < b.age; }

void springAndSummer() {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      deque<int> newTrees;
      int deadNutrients = 0;
      for (int age : trees[i][j]) {
        if (land[i][j] >= age) {
          land[i][j] -= age;
          newTrees.push_back(age + 1);
        } else {
          deadNutrients += age / 2;
        }
      }
      land[i][j] += deadNutrients;
      trees[i][j] = newTrees;
    }
  }
}

void autumn() {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      for (int age : trees[i][j]) {
        if (age % 5 == 0) {
          for (int dir = 0; dir < 8; dir++) {
            int ny = i + dy[dir];
            int nx = j + dx[dir];
            if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
            trees[ny][nx].push_front(1);
          }
        }
      }
    }
  }
}

void winter() {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      land[i][j] += a[i][j];
    }
  }
}

int main() {
  cin >> n >> m >> k;
  land.assign(n, vector<int>(n, 5));
  a.assign(n, vector<int>(n));
  trees.assign(n, vector<deque<int>>(n));

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> a[i][j];
    }
  }

  for (int i = 0; i < m; i++) {
    int tr, tc, tage;
    cin >> tr >> tc >> tage;
    trees[tr - 1][tc - 1].push_back(tage);
  }

  while (k--) {
    springAndSummer();
    autumn();
    winter();
  }

  int result = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      result += trees[i][j].size();  // 살아남은 나무의 수 계산
    }
  }

  cout << result;

  return 0;
}