Задача 76: Калькулятор

Условие задачи:

Имеется калькулятор, который выполняет три операции:
1. Прибавить к числу X единицу.
2. Умножить число X на 2.
3. Умножить число X на 3.
Определите, какое наименьшее число операций необходимо для того, чтобы получить из числа 1 заданное число N.

Входные данные:

Программа получает на вход одно число, не превосходящее \(10^6\).

Выходные данные:

Требуется вывести одно число: наименьшее количество искомых операций.

Решение:

n = int(input())

dp = [0] * (n + 1)

for i in range(2, n + 1):
    dp[i] = dp[i - 1]
    if i % 2 == 0 and dp[i // 2] < dp[i]:
        dp[i] = dp[i // 2]
    if i % 3 == 0 and dp[i // 3] < dp[i]:
        dp[i] = dp[i // 3]
    dp[i] += 1
    
print(dp[n])

У вас включен блокировщик рекламы. Пожалуйста, выключите его чтобы увидеть решения. На этом сайте не так много рекламы, а кушать что-то надо. Вот котик