1로 만들기

정수 x가 주어질 때 정수 x에 사용할 수 있는 연산은 다음과 같이 4가지이다

a. x가 5로 나누어떨어지면 5로 나눈다

b. x가 3으로 나누어떨어지면 3으로 나눈다

c. x가 2로 나누어떨어지면 2로 나눈다

d. x에서 1을 뺀다

 

정수 x가 주어졌을 때 연산 4개를 적절히 사용해서 1을 만들려고 한다

연산을 사용하는 횟수의 최솟값을 출력하시오

 

입력조건

→ 첫째 줄에 정수 x가 주어진다

 

출력조건

→ 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다

 

# [이코테] 1로 만들기
number = int(input())
table = [0] * 30001
for i in range(2, number+1):
    table[i] = table[i-1] + 1
    if i % 5 == 0:
        table[i] = min(table[i], table[i//5]+1)
    if i % 3 == 0:
        table[i] = min(table[i], table[i//3]+1)
    if i % 2 == 0:
        table[i] = min(table[i], table[i//2]+1)
print(table[number])