4. 그리디 알고리즘 : 1이 될 때 까지

rule:

N이 1이 될 때까지 두 가지 연산만 수행할수 있다. 두 가지 연산을 수행해야 하는 최소 횟수를 구하시오.

 1. N에서 1을 뺀다.

 2. N을 K로 나눈다. (나눠질 경우에만 가능)

 

조건 :

N과 K는 2보다 큰 자연수

 

info :  

가능하면 빼는 것 보다 무조건 나누는 것이 좋다.

 

n, k = map(int, input().split())

count = 0

while n != 1 :
  
  if n % k == 0:
    n /= k
    count += 1

  elif n % k != 0:
    n -= 1
    count += 1


print(count)

하지만 위보다 시간 복잡도를 줄여할 경우 -1을 연산의 횟수를 간단하게 구하는 방법을 이용해서 

한꺼번에 빼줄 수 있습니다. n의 몫에 k를 곱해주고 num에다가 저장을 해주면 n  -1을 한꺼번에 값이 됩니다. 

원래 n의 값에다 num을 빼주면 -1을 해준 연산의 횟수가 나옵니다.

그리고 그것에다 k를 나눠준 후 연산의 횟수에 1을 더해주고 위 과정을 반복하면 n이 k보다 작아집니다.

그럼 더이상 n을 k로 나눌 수 없기 때문에 (n-1)의 횟수로 -1의 연산을 해주게 됩니다.

n, k = map(int,input().split())

count = 0

while(True) :
  num = (n//k) * k
  count += n - num
  n = num

  if n < k :
    break;

  n /= k
  count += 1

count += (n-1)

print(count)