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

로직

0. X 를 입력받는다
1. 크기가 3만개인 리스트를 만들고 0 으로 초기화
2. x[0]=1
3. for i in range (2,X+1):
   2 ~ X 까지 반복
4. -1 의 경우
5. i%2==0
6. i%3==0
   7.i%5==0

<< 점화식 >>
x[i]=min(x[i-1],x[i/2],x[i/3],x[i/5])+1

코드

X = int(input())
x = [0] * 30001

for i in range (2,X+1):
  # 현재 수에서 1빼는 경우
  x[i] = x[i-1] + 1

  # 현재 수가 2,3,5로 나누어 떨어지는 경우
  # --> x[i]값을 작은애로 대체
  if i%2==0:
    x[i] = min(x[i],x[i//2]+1)
  if i%3==0:
    x[i] = min(x[i],x[i//3]+1)
  if i%5==0:
    x[i] = min(x[i],x[i//5]+1)

print(x[X])

주의사항

• X는 1~30,000까지 가능하다
  -> 리스트를 30001까지 만들어주기
• 점화식을 이해하는 것이 중요하다
• +1을 해주는 이유 : 함수의 호출 횟수를 구해야하기 때문이다