[Python] 1로 만들기

문제

• 정수 X가 주어질때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다.
  • 1) X가 5로 나누어떨어지면, 5로 나눈다.
  • 2) X가 3으로 나누어 떨어지면, 3으로 나눈다.
  • 3) X가 2로 나누어 떨어지면, 2로 나눈다.
  • 4) X에서 1을 뺀다.
• 정수 X가 주어졌을때, 연산 4개를 적절히 사용해서 1을 만들려고 한다.
• 연산을 사용하는 횟수의 최솟값을 출력하시오.
• 예를 들어, 정수가 26이면 다음과 같이 계산해서 3번의 연산이 최솟값이다.
  • 26 - 1 = 25
  • 25 / 5 = 5
  • 5 / 5 = 1

입력

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

출력

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

문제 풀이

• 모든 수에 1을 빼는 연산이 가능
• 1을 빼는 경우로 가정하고 계산한 후, 만약 2, 3, 5로 나누어 떨어진다면, 각각의 [//2],[//3],[//5] 인덱스 값 + 1을 한 경우와 1을 빼는 연산을 한 경우를 비교해 최솟값을 인덱스에 저잫
• 마지막 인덱스에 필요한 연산 수가 들어있으므로 마지막 인덱스 값 출력

코드

x = int(input())
dp = [0] * (x + 1)
# 0과 1은 1로 만들 필요가 없으므로 dp[0], dp[1]의 값은 0 -> 2부터 탐색
for i in range(2, x + 1):
    # 모든 수에서 1을 뺄 수 있음
    dp[i] = dp[i - 1] + 1
    # 2, 3, 5로 나눌 수 있는 경우
    if (dp[i] % 5 == 0):
        dp[i] = min(dp[i // 5] + 1, dp[i])
    if (dp[i] % 3 == 0):
        dp[i] = min(dp[i // 3] + 1, dp[i])
    if (dp[i] % 2 == 0):
        dp[i] = min(dp[i // 2] + 1, dp[i])


print(dp[x])