📌 [BOJ] 백준 1463 1로 만들기

📖 문제

📖 예제

📖 풀이

N = int(input())
dp = [0] * (N+1)
for i in range(2, N+1):
  dp[i] = dp[i-1] + 1

  if i % 2 == 0:
    dp[i] = min(dp[i], dp[i//2]+1)
  if i % 3 == 0:
    dp[i] = min(dp[i], dp[i//3]+1)

print(dp[N])

본 문제는 다음의 과정을 거친다.
1. 바로 직전 수에 1을 더한것을 가정하여 직전 dp 테이블에 +1을 한 수로 갱신
2. 2로 나누어지는 경우 1에서 갱신한 값과 비교해 더 작은 수로 갱신
3. 3으로 나누어지는 경우 1 혹은 2에서 갱신한 값과 비교해 더 작은 수로 갱신

N+1개 만큼의 dp테이블을 만든 후 2부터 for문을 시작한다.
기본적으로 전에 입력한 수에 1을 더하는 과정으로 dp테이블을 갱신한다.
만약 해당 수가 2 혹은 3으로 나누어지는 수일 경우 기존 dp 테이블에 갱신된 수와 비교했을 때 더 작은 수로 해당 값을 갱신한다.