[python] 1로 만들기

1) X가 5로 나누어 떨어지면, 5로 나눔

2) X가 3으로 나누어 떨어지면, 3으로 나눔

3) X가 2로 나누어 떨어지면, 2로 나눔

4) X에서 1을 뺌

- 4가지 연산을 사용해서 1로 만듦

- 최소 연산 횟수 출력

 

x = int(input())

# DP 테이블 초기화
d = [0] * 1000001

# 다이나믹 프로그래밍 (보텀업)
for i in range(2, x + 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])