17. 다이나믹 프로그래밍 : 1로 만들기

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

1. X가 5로 나누어진다면, 5로 나눈다.

2. X가 3로 나누어진다면, 3으로 나눈다.

3. X가 2로 나누어진다면, 2로 나눈다.

4. X에서 1을 뺀다.

 

정수 X가 주어졌을 때 연산 횟수의 최솟값을 출력하시오.

 

count = 0

def five_divide (x):
  global count
  count += 1
  return x/5
 
def three_divide (x):
  global count
  count += 1
  return x/3

def two_divide (x):
  global count
  count += 1
  return x/5

def one_minus (x):
  global count
  count += 1
  return x-1

num = int(input())

while num != 1 :
  if (num -1) % 5 == 0:
    num = one_minus(num)
    num = five_divide(num)
  elif num % 5 == 0:
    num = five_divide(num)
  elif num % 3 == 0:
    num = three_divide(num)
  elif num % 2 == 0:
    num = two_divide(num)
  else:
    num = one_minus(num)
print(count)

나는 그냥 그리디처럼 풀었다. ㅠㅠ

그냥 5로 나누거나 항상 -1을 했을 때 5로 나누어질 때 연산의 최솟값이 나온다고 추정을 했다.

우선 위 코드가 예제 input을 입력할 때 정답은 나오는데 이게 어느 숫자에나 적용되는 코드인지 모르겠다는게 문제..

 

x = int(input())

d = [0] * 30001

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[x])

아 이해 됬다. ㅋㅋ 아 재밋네