[백준] 2655 가장높은탑쌓기 - javascript

📌 문제

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

📌 풀이

let input = require("fs").readFileSync("/dev/stdin").toString().split("\n");
let n = Number(input[0]);
let stones = new Array(n);
for (let i = 0; i < stones.length; i++) {
  // stones -> 넓이, 높이, 무게, 그 벽돌의 index
  stones[i] = new Array(4);
}
for (let i = 0; i < n; i++) {
  stones[i] = input[i + 1].split(" ").map(Number);
  stones[i][3] = i + 1;
}
stones.sort((a, b) => a[0] - b[0]); // 밑면넓이 기준 오름차순정렬
// dp[n] = n번째 상자를 쌓았을 때 가능한 최대높이
let dp = new Array(n).fill(0);

// 각 상자의 높이로 초기화
for (let i = 0; i < n; i++) {
  dp[i] = stones[i][1];
}

for (let i = 1; i < n; i++) {
  for (let j = 0; j < i; j++) {
    // 밑면의 넓이는 오름차순이므로 당연히 i가 j보다 크다
    // 따라서 무게가 더 큰경우에만 넣을 수 있음
    if (stones[j][2] < stones[i][2]) {
      dp[i] = Math.max(dp[i], stones[i][1] + dp[j]);
    }
  }
}

let max = Math.max(...dp);
let answer = []; // 길이가 벽돌의 수
// 쌓은 벽돌 추적하기
for (let i = dp.length - 1; i >= 0; i--) {
  if (max == dp[i]) {
    answer.push(stones[i][3]);
    max -= stones[i][1];
  }
}
console.log(answer.length);
answer.reverse();
answer.forEach((a) => console.log(a));

✔ 알고리즘 : DP

✔ stones 배열에는 넓이, 높이, 무게, 그 벽돌의 index정보가 들어가는 2차원 배열

✔ stones를 밑면넓이 기준으로 오름차순 정렬

✔ dp[n] : n개의 상자를 쌓았을 때 가능한 최대높이이고 dp[n]을 n번째 stone의 높이로 초기화한 상태로 dp를 진행

✔ 벽돌을 위에서부터 쌓을 수 있는 조건 : 밑면의 넓이와 무게가 같이 증가해야한다

✔ 이미 밑면넓이기준 오름차순 정렬했으므로 i,j 2중 for문에서 밑면넓이는 볼 필요가 없고 넓이만 보고 i보다 j가 작으면 아래로 쌓을 수 있는 벽돌이 된다. (저의 풀이 방식은 위에서부터 탑을 아래로 쌓는 방식입니다)

✔ 계속 진행하며 dp값 갱신

✔ dp배열의 최댓값이 쌓을 수 있는 탑의 최대높이

✔ dp배열을 역순으로 추적해서 탑이 어떻게 쌓였는지 answer에 저장하고 reverse 하여 출력

✔ 난이도 : 백준 기준 골드3