글 읽기 - 100% 메모리 초과 질문 있습니다

feel321 1년 전 0

아래 코드에 1번 코드와 2번 코드가 있는데요
각각 상황에 대해서 질문이 있습니다

질문1
1번 코드는 100%에서 메모리 초과가 발생합니다
혹시 잘못 작성된 부분이 있을까요?

질문2
2번 코드는 맨 처음 작성한 초기코드인데요
35% 쯤에서 메모리 초과가 납니다
Array().fill(0)으로 정렬해놓고 계산하지 않고, 값을 계산하고 push하는식으로 했는데요
이방법이 원래 더 느리고 비효율적인가요?

// 1번 코드
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "../input.txt";

let input = fs.readFileSync(filePath).toString().trim().split("\n");
input = Number(input);

console.log(solution(input));

function solution(input) {
  const dp = Array(input + 1).fill(0);
  let idx = 2;

  while (!dp[input]) {
    dp[idx] = dp[idx - 1] + 1;

    if (idx % 3 === 0) {
      dp[idx] = Math.min(dp[idx], dp[idx / 3] + 1);
    }
    if (idx % 2 === 0) {
      dp[idx] = Math.min(dp[idx], dp[idx / 2] + 1);
    }
    idx += 1;
  }
  return dp[input];
}

// 2번 코드
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "../input.txt";

let input = fs.readFileSync(filePath).toString().trim().split("\n");
input = Number(input);

console.log(solution(input));

function solution(input) {
  const dp = [-1, 0, 1, 1];

  while (!dp[input]) {
    const nextIndex = dp.length;

    let next = dp[nextIndex - 1];
    if (nextIndex % 2 === 0) {
      next = Math.min(next, dp[nextIndex / 2]);
    }
    if (nextIndex % 3 === 0) {
      next = Math.min(next, dp[nextIndex / 3]);
    }
    dp.push(next + 1);
  }
  return dp[input];
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

100% 메모리 초과 질문 있습니다

feel321 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말