ch8_2_sol.py

#교재 솔루션
#1부터 증가시키는 방향으로
#최소 횟수 생성
#아이디어가 좋네..

x = int(input())

d = [0]*100

for i in range(2, x+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)
    
    if i % 5 == 0:
        d[i] = min(d[i], d[i//5]+1)

print(d)

#내가 한 방식이랑 어떤게 연산 횟수가 더 많을까..
#이 방식은 1에서 X까지 다 처리
#내가 한 방식은 X에서 부터 경우를 따지면서 1로 내려옴
#연산 횟수는 내 방식이 더 적은거 아닌가?