[알고리즘] 그리디 알고리즘 - 1이 될 때까지

*출처:https://www.youtube.com/watch?v=2zjoKjt97vQ&t=2359s

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

result = 0

while True:
    # n이 k로 나누어 떨어지는 수가 될 때까지 빼기
    tmp = (n//k) * k
    result += n - tmp
    n = tmp
    # 더이상 나눌 수 없을 때 반복문 탈출
    if n < k:
        break
    n //= k
    result += 1

result += (n-1)
print(result)