[백준/G3] 16235 나무 재테크

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

시간복잡도

O(

풀이

각 4계절에 따라 나무와 양분을 관리하여 살아있는 나무의 갯수를 구하는 문제

주어진 조건대로 단순구현하면 되는 문제였다.
처음엔 봄과 여름을 따로 작성했지만 동시에 작동해도 되는거라 합치는 경우도 작성해봤다.
사실 봄/여름을 거치는 업데이트만 잘 수행하는 것이 관건인 듯 하다.

• 바로 해당 값에 업데이트를 하는 것이 아닌, 살아있는 나무 리스트(alive)와 deadTree, leftFood이렇게 3가지 변수를 적절히 옮겨가며 로직을 수행한다.

const dx = [1, 0, -1, 0, 1, 1, -1, -1];
const dy = [0, -1, 0, 1, 1, -1, -1, 1];

// 봄 : 나이만큼 양분을 먹고, 나이가 1 증가
// 여러개의 나무가 있다면 나이가 어린 나무부터 먹으며, 나이만큼 못먹을시 즉사
function springandsummer() {
  // food
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      let temp = tree[i][j];
      temp.sort((a, b) => a - b);
      let alive = [];
      let deadTree = 0;
      let leftFood = food[i][j];
      for (let t = 0; t < temp.length; t++) {
        let age = temp[t];
        if (age <= leftFood) {
          leftFood -= age;
          alive.push(age + 1);
        } else {
          deadTree += Math.floor(age / 2);
        }
      }
      tree[i][j] = alive;
      food[i][j] = leftFood + deadTree;
    }
  }
}

// 가을 : 나이가 5의배수인 나무 번식, 주변 8개 칸에 나이가 1인 나무 생성
function autumn() {
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      for (let t of tree[i][j]) {
        if (t % 5 === 0) {
          for (let d = 0; d < 8; d++) {
            let nx = i + dx[d];
            let ny = j + dy[d];
            if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
            tree[nx][ny].push(1);
          }
        }
      }
    }
  }
}

// 겨울 : 양분추가
function winter() {
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      food[i][j] += plus[i][j];
    }
  }
}

// K년이 지난 후 살아남은 나무의 수
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./16235.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const [N, M, K] = input[0].split(" ").map(Number);
const plus = [];
const tree = Array.from({ length: N }, () =>
  Array.from({ length: N }, () => [])
);

const food = Array.from({ length: N }, () =>
  Array.from({ length: N }, () => 5)
);


for (let i = 1; i < N + 1; i++) {
  plus.push(input[i].split(" ").map(Number));
}

for (let i = 1 + N; i < M + N + 1; i++) {
  let [r, c, age] = input[i].split(" ").map(Number);
  tree[r - 1][c - 1].push(age);
}

for (let k = 0; k < K; k++) {
  // spring();
  // summer();
  springandsummer();
  autumn();
  winter();
}

let ans = 0;
for (const line of tree) {
  for (const tline of line) {
    ans += tline.length;
  }
}

console.log(ans);

44172kb 916ms