[이것이 코딩테스트다] 1로 만들기

🗃️문제 설명

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

• X가 5로 나누어떨어지면, 5로 나눈다.
• X가 3으로 나누어 떨어지면, 3으로 나눈다.
• X가 2로 나누어 떨어지면, 2로 나눈다.
• X에서 1을 뺀다.

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

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

예를 들어, 정수가 26이면 다음과 같이 계산해서 3번의 연산이 최솟값이다.

• 26 - 1 = 25
• 25 / 5 = 5
• 5 / 5 = 1

첫째 줄에 정수 X이 주어진다. (1 ≤ X ≤ 30,000)

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

🖥️코드

import sys
input = sys.stdin.readline

X = int(input())

memoization = [0] * 30001

# 역연산 정리
# X에 5를 곱한다.
# X에 3을 곱한다.
# X에 2를 곱한다.
# X에 1을 더한다.
for x in range(2, X+1):
    memoization[x] = memoization[x-1] + 1   # 현재 넘버 1 : 만들 넘버 : 2 → 1을 더해주면 된다.
    if x % 2 == 0:
        memoization[x] = min(memoization[x], memoization[x // 2] + 1)
    if x % 3 == 0:
        memoization[x] = min(memoization[x], memoization[x // 3] + 1)
    if x % 5 == 0:
        memoization[x] = min(memoization[x], memoization[x // 5] + 1)
print(memoization[x])

🔒문제 출처 및 참고 코드

이것이 코딩테스트다 with 파이썬 - 1로 만들기
모범 답안 - 1로 만들기