[BOJ 1463] 1로 만들기

문제

1로 만들기

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

 

 

풀이

설명

정수 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

 

예시 코드

function solution() {
  const N = +input();
  const dp = 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];
}