[백준/파이썬] 1463 1로 만들기

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

---

알고리즘 분류

• 다이나믹프로그래밍

문제풀이

다이나믹프로그래밍의 전형적인 문제이다.
그리디 식으로 접근하면 안된다..

d[i]는 i를 1로 만들기 위한 연산 횟수를 저장한다.
d[0]이나 d[1]은 1로 만들기 위한 연산 횟수가 0이므로 그대로 0,
N이 10의 6제곱일때의 인덱스는 10의 6제곱이므로 d의 범위는 10**6+1까지이다.

소스코드

n=int(input())
d=[0]*(10**6+1)

for i in range(2, n+1):
  d[i]=d[i-1]+1
  if i%2==0:
    d[i]=min(d[i], d[i//2]+1)
  if i%3==0:
    d[i]=min(d[i], d[i//3]+1)

print(d[n])