백준 - 1로 만들기(1463번) [JS]

백준 - 1로 만들기(1463번)

문제는 간단하지만 푸는 방법을 고민하는 것이 어려웠다. 스스로 풀지 못하고 다른 사람들의 풀이를 참고하여 풀었다. DP 방법을 사용했다.
동적 계획법(Dynamic Programming, DP)은 문제를 작은 하위 문제로 나누고, 그 결과를 저장하여 전체 문제를 해결하는 방법이다. 즉, 중복 계산을 줄여 효율적으로 문제를 해결하는 기법이다.

코드 설계

문제 해결의 단계는 아래와 같다.

1. N으로 숫자를 입력받는다. dp 배열을 생성하여 N개만큼 0으로 초기화한다.
2. 1은 이미 0으로 초기화되었으므로, 2부터 N까지 돌면서 연산의 최솟값을 구해 초기화한다.
3. -1을 하는 조건은 항상 실행될 수 있으므로 기본적으로 실행하여 -1을 했을때의 연산횟수와 2를 나눴을때의 연산 횟수, 3을 나눴을 때의 연산횟수를 비교하며 각 숫자의 최소 연산횟수를 배열에 채워나간다.

제출한 답

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

const N = input[0];
const dp = new Array(N + 1).fill(0);

// dp[1] = 0 (이미 초기화됨)
for (let i = 2; i <= N; i++) {
  dp[i] = dp[i - 1] + 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);
}

console.log(dp[N]);

💡한줄평

스스로 풀어내지 못한 첫 번째 문제라 좀 답답했다. 다른 사람들의 풀이 방식을 보니 정말 간단한 방법인데 이걸 생각해내지 못한 것이 아쉽다. 그래도 DP라는 방식에 대해서 알아보는 시간을 가진 것 같아서 의미있었다. 다음에 비슷한 문제를 풀어봐야겠다.