[BOJ 12852] 1로 만들기 2

문제

1로 만들기 2

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

 

 

풀이

설명

정수 X를 1로 만들기 위해 필요한 연산의 최소 횟수를 구하는 문제입니다.

 

사용할 수 있는 연산은 다음과 같습니다.

1. X가 3으로 나누어 떨어지면, 3으로 나눕니다.
2. X가 2로 나누어 떨어지면, 2로 나눕니다.
3. 1을 뺍니다.

 

DP를 사용해 해결할 수 있습니다.

 

dp[i]는 i를 만드는 데 필요한 연산의 최소 횟수입니다.

 

점화식은 다음과 같습니다.

dp[i]는 다음 세 가지 값 중 최솟값입니다.

1. dp[i - 1] + 1
2. i가 2로 나누어 떨어지는 경우, dp[i / 2] + 1
3. i가 3으로 나누어 떨어지는 경우, dp[i / 3] + 1

 

추가적으로 경로 배열을 하나 만들어, dp 값이 업데이트 될 때마다 경로를 저장합니다.

dp 배열을 모두 채우고 나면, 경로 배열을 통해 경로를 역추적합니다.

 

예시 코드

function solution() {
  const N = Number(input());
  const dp = Array(N + 1).fill(0);
  const path = Array(N + 1).fill(0);

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

    if (i % 2 === 0 && dp[i] > dp[i / 2] + 1) {
      dp[i] = dp[i / 2] + 1;
      path[i] = i / 2;
    }
    if (i % 3 === 0 && dp[i] > dp[i / 3] + 1) {
      dp[i] = dp[i / 3] + 1;
      path[i] = i / 3;
    }
  }

  const result = [];
  let curr = N;
  while (curr > 0) {
    result.push(cur);
    cur = path[cur];
  }

  return [dp[N], result.join(" ")].join("\n");
}