백준) 1463 - 1로 만들기 JS

📌 문제 링크

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

---

📌 문제 탐색하기

• 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지이다.
• X가 3으로 나누어 떨어지면, 3으로 나눈다.
• X가 2로 나누어 떨어지면, 2로 나눈다.
• 1을 뺀다.
• 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다.
• 연산을 사용하는 횟수의 최솟값을 출력해라.

시간복잡도

• 2부터 N까지 각 숫자에 대해 한 번씩만 계산을 수행하므로 O(n)

알고리즘 선택

• dp

---

📌 코드 설계하기

1. 문제의 `input`을 숫자로 변환합니다.
2. 최소값을 구할 함수인 `reduceInput`을 선언합니다.
3. `dp`배열을 `input + 1` 크기만큼 생성하고 `0`으로 채워줍니다.
4. 2부터 `input`까지 반복하면서 1을 빼는 경우, 2로 나누어 떨어지는 경우, 3으로 나누어 떨어지는 경우를 각각 실행하면서 결과와 비교한 최소 값을 `dp`배열에 저장합니다.
5. 해당되는 `dp[n]`을 출력합니다.

---

📌 정답 코드

//https://www.acmicpc.net/problem/1463
export {};

const fs = require("fs");
const filePath =
  process.platform === "linux" ? "/dev/stdin" : __dirname + "/input2.txt";
const input = Number(fs.readFileSync(filePath).toString().trim().split("\n"));

const reduceInput = (n: number) => {
  const dp = new Array(n + 1).fill(0);

  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + 1;
    if (i % 2 === 0) {
      dp[i] = Math.min(dp[i], dp[i / 2] + 1);
    }
    if (i % 3 === 0) {
      dp[i] = Math.min(dp[i], dp[i / 3] + 1);
    }
  }
  return dp[n];
};

console.log(reduceInput(input));