[백준] 4902번, 삼각형의 값 (JavaScript)

Algorithm

문제 정보 : 삼각형의 값 (Easy)

• 문제 분류 : 알고리즘 연습 중급 1/3, 이분탐색 (연습)
• 문제 출처 : 백준 골드 2, 삼각형의 값 (Easy)

시작하며 ✅

이 문제 역시 풀이까지는 빨리 했지만 시간 초과 문제를 해결하는데 상당히 애를 먹었다.

접근 과정

각각의 삼각형들의 합을 어떻게 구할까 고민하던 중, 삼각형을 정삼각형과 역삼각형을 각각 구하여 최대값을 구하는 방식으로 접근했다. 인자로 구할 삼각형의 높이를 입력 받고 삼각형 배열에서 필요한 범위만큼을 누적하여 계산하는 방식으로 구현했다. 이 방법으로 구현할 시, 4중 for문 y, x, 필요한 높이만큼 반복, 필요한 x 범위까지 반복하는 과정이 필요하여 결국 시간 초과가 발생했다.

다른 풀이를 참고하였더니 부분적으로 DP, 즉, 누적합을 미리 만들어두고 3중 for문 y, x, 필요한 높이만큼 반복으로만 구현하는 방식으로 풀이를 바꾸었다. 이 방법을 통해 통과할 수 있었다.

풀이 과정 ✨

1. 미리 삼각형의 누적합 배열을 만들어둔다.
2. 반복문을 돌며, 정삼각형과 역삼각형을 각각 만든 후, 최대값을 구한다.

코드 (시간초과 풀이)

// const readFileSyncAddress = '/dev/stdin';
const readFileSyncAddress = "text.txt";

let input = require("fs")
  .readFileSync(readFileSyncAddress)
  .toString()
  .split("\n");

function solution(line) {
  const nums = line.split(" ").map(Number);
  const H = nums[0];
  const accMap = Array.from({ length: H }, () => []);

  let curHeight = 0;
  let cnt = 0;
  let result = -Infinity;

  let lineAcc = 0;
  for (let i = 1; i <= nums.length && curHeight < H; i++) {
    lineAcc += nums[i];
    accMap[curHeight].push(lineAcc);
    cnt++;

    if (cnt === (curHeight + 1) * 2 - 1) {
      curHeight++;
      cnt = 0;
      lineAcc = 0;
    }
  }

  getDownTri();
  getUpTri();

  return result;

  function getDownTri() {
    // 삼각형의 꼭짓점을 먼저 찾고
    for (let i = H - 1; i > 0; i--) {
      for (let j = 1; j < accMap[i].length; j += 2) {
        let preSum = 0;

        for (let k = i; k > 0; k--) {
          let start = j - (i - k) * 2;

          // 역삼각형의 시작이 0보자 작으면 성립 안 됨
          if (start < 0) continue;
          // 역삼각형의 마지막 위치가 꼭짓점까지 와야 함.
          if (j >= accMap[k].length) continue;

          preSum += accMap[k][j] - accMap[k][start - 1];
          result = Math.max(result, preSum);
        }
      }
    }
  }

  function getUpTri() {
    // 삼각형의 꼭짓점을 먼저 찾고
    for (let i = 0; i < H; i++) {
      for (let j = 0; j < accMap[i].length; j += 2) {
        let preSum = 0;

        for (let k = i; k < H; k++) {
          preSum += accMap[k][j + (k - i) * 2];

          // 누적값의 시작이 0이 아닌 경우
          // 이전 값을 빼줘야 함.
          if (j > 0) {
            preSum -= accMap[k][j - 1];
          }

          result = Math.max(result, preSum);
        }
      }
    }
  }
}

let answer = "";
let idx = 0;
while (input[idx][0] !== "0") {
  answer += `${idx + 1}. ${solution(input[idx])}\n`;
  idx++;
}

console.log(answer.trimEnd());

마치며 🚩

생각보다 많이 어려웠던 문제였다. 풀면서도 시간 초과가 발생할 거 같다고 느꼈는데 결국 시간 초과가 발생했고 이를 해결하는 방법도 직접 떠올리지 못했다.. 더 열심히 풀어보자.