백준 SILVER 1(1로 만들기 2) - #12852

image

  • 사용 언어 : javascript

  • 해결 날짜 : 2023-02-11

  • 해결 방법 :

    • dp를 활용해 문제 해결
    • dp 별 1번 인덱스: 연산의 최솟값, 2번 인덱스: 경로
    • dp의 각 값을 1뺀 경우, 2로 나누는 경우, 3으로 나누는 경우 중 최솟값으로 업데이트

  • 회고 :

    • x

  • 코드

    const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : '../input.txt';
const input = fs.readFileSync(filePath).toString().trim();

solution(input);

function solution(props) {
  const N = +props;
  const dp = Array.from({ length: N + 1 }, (_, i) => [0, i === 1 ? [1] : []]);

  for (let i = 2; i <= N; i++) {
    dp[i][0] = dp[i - 1][0] + 1;
    dp[i][1] = [...dp[i - 1][1], i];

    if (i % 3 === 0 && dp[Math.floor(i / 3)][0] + 1 < dp[i][0]) {
      dp[i][0] = dp[Math.floor(i / 3)][0] + 1;
      dp[i][1] = [...dp[Math.floor(i / 3)][1], i];
    }

    if (i % 2 == 0 && dp[Math.floor(i / 2)][0] + 1 < dp[i][0]) {
      dp[i][0] = dp[Math.floor(i / 2)][0] + 1;
      dp[i][1] = [...dp[Math.floor(i / 2)][1], i];
    }
  }

  console.log(`${dp[N][0]}\n${dp[N][1].reverse().join(' ')}`);
}

  • 출처: 백준