[다이나믹 프로그래밍] 1로 만들기

아래 영상 36:35초 문제입니다.

https://www.youtube.com/watch?v=5Lu34WIx2Us&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=6

---

import sys
input=sys.stdin.readline

x=int(input())

#x가 5로 나누어 떨어지면, 5로 나누기
#x가 3으로 나누어 떨어지면, 3으로 나누기
#x가 2로 나누어 떨어지면, 2로 나누기
#그 외의 경우, x에서 1빼기

#연산 횟수를 최소화하며 1 만들기

#아이디어 : 그리디가 아니기 때문에 무조건 나눈다고 연산이 줄어드는 게 아님

#점화식 : 최소 연산 횟수 = min(i를 4가지 연산을 하여 나온 각각의 값)+1
#1을 더하는 이유 : 하나의 연산이 수행된 것이기 때문

#dp 테이블 초기화
d=[0]*30001 #x가 0부터 30000까지 들어올 수 있기 때문에 

#바텀업 방식
for i in range(2, x+1):  #2부터 x까지
  # 점화식 : 4가지 경우 중에서 가장 작은 값을 가지는 것을 골라서 1 더함
  #현재의 수에서 1을 빼는 경우
  d[i]=d[i-1]+1
  #2로 나누어 떨어지는 경우
  if i%2==0:
    d[i]=min(d[i],d[i//2]+1)
  #3으로 나누어 떨어지는 경우
  if i%3==0:
    d[i]=min(d[i],d[i//3]+1)
  #5로 나누어 떨어지는 경우
  if i%5==0:
    d[i]=min(d[i],d[i//5]+1)
print(d[x])

DP 너란 짜식 어렵구나..

점화식 생각해내는 게 어려운데, 동빛나씨가 코테에서 나오는 DP 문제는 대부분 점화식이 비슷하다고 했기때문에 DP문제를 앞으로 많이 풀어보며 점화식을 바로 생각해낼 수 있을 정도로 익혀야겠다.
화이팅구리 

---