[백준 1463/javascript] 1로 만들기

'적은 시간이 주어지고, 매 차례마다 선택지를 고르며 최소한의 선택 수를 만들어라'
-  다이나믹 프로그래밍
.

계산 이전의 경우 + 1의 수를 갖는다면 다이나믹 프로그래밍을 시도해보자

특히나 시간 제한이 있고 그 시간이 적다면 더더욱 다이나믹 프로그래밍인지 의심해보자

선택지를 통한 최소 선택시의 수, 적은 시간 등은 이 문제가 다이나믹 프로그래밍으로 풀 근거가 된다

일부 풀이에서는 다이나믹 프로그래밍과 재귀를 혼동하곤 하는데

재귀는 top-down 방식으로 n 에서 n-1 로 내려오며 base 조건에서 리턴하여 푸는 방법이고

다이나믹 프로그래밍은 bottom-up 방식으로 최소범위값 (여기서는 1) 부터 1씩 늘려가며

값이 될 수 있는 하위 요소들을 분석하며 로직을 찾아 배열로 쌓아가며 찾는 방식이다

요약하면, 입력한 수n +1 이상의 배열을 만들어 예상 입력 수를 인덱스로 가지며 그 값을 경우의 수로 갖도록 하고

최저 범위일때 부터 경우의 수를 구하고 배열에 저장, 규칙을 찾으며, 규칙이 적용되는 수부터는

따로 예외로 명시하지 않고 반복문을 통해 입력한 수 n 까지 배열을 채워나가주면 된다

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

1463번: 1로 만들기

const readline = require("readline").createInterface({
  input: process.stdin,
  output: process.stdout,
});

readline.on("line", (line) => {
  input = Number(line);
});

readline.on("close", () => {
  solution(input);
  process.exit();
});

const solution = (n) => {
  // bottom-top 방식의 다이나믹 프로그래밍을 위해 해당 수를 인덱스로 갖고 최소 연산값을 값으로 갖는 배열을 만든다
  const dp = new Array(n + 4); // 배열 크기에 약간의 여유를 주자
  // 규칙을 찾기위해 bottom 부터 채워나간다. 규칙에 적용 되기 전은 예외로 둬야하니 냅둔다
  dp[1] = 0;
  dp[2] = dp[1] + 1;
  dp[3] = Math.min(dp[1] + 1, dp[2] + 1);
  // dp[4] 이후로는 규칙에 수렴하므로 주석처리
  // dp[4] = Math.min(dp[4-1] + 1, dp[4/2] + 1);
  // dp[5] = Math.min(dp[5-1]+1)
  // dp[6] = Math.min(dp[6/2] + 1, dp[6/3] + 1, dp[6-1]+1)
  // dp[7] = Math.min(dp[7-1]+1)
  // dp[8] = Math.min(dp[8/2]+1, dp[8-1]+1)
  // dp[9] = Math.min(dp[9/3]+1, dp[9-1]+1)
  // dp[10] = Math.min(dp[10/2]+1, dp[10-1]+1)

  //찾은 규칙에 맞게 반복문으로 배열을 채워 나간다
  for (let i = 4; i <= n; i++) {
    // 2로도 3으로도 나누어 떨어지는 수는 이전 경우가 3가지 경우를 가진다
    if (i % 2 === 0 && i % 3 === 0) {
      dp[i] = Math.min(dp[i / 2] + 1, dp[i / 3] + 1, dp[i - 1] + 1);
    } else if (i % 2 === 0) {
      dp[i] = Math.min(dp[i / 2] + 1, dp[i - 1] + 1);
    } else if (i % 3 === 0) {
      dp[i] = Math.min(dp[i / 3] + 1, dp[i - 1] + 1);
    } else {
      dp[i] = dp[i - 1] + 1;
    }
  }
  // 배열로 저장한 n 일때의 연산 최소값을 출력한다
  console.log(dp[n]);
};