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

 

k로 나눌 수 있는 만큼 나누고 나머지는 -1을 반복해서 수행하는 방식으로 해결하면 된다.

 

n,k = map(int,input().split())
result = 0
while True:
    # n보다 작거나 같은 수 중 k로 나누어떨어지는 가장 큰 수
    target = (n//k)*k
    # -1을 수행해야 하는 횟수를 계산한 것
    result += (n-target)
    n = target

    # n이 k로 나눠떨어지지 않는다면
    # -1을 수행해야 하니 반복문 탈출
    if n<k:
        break
    result += 1
    n //= k

# n이 1이 될 때까지 -1을 수행해야 하는 횟수
result += (n-1)
print(result)

 

출처 
https://www.youtube.com/watch?v=2zjoKjt97vQ&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=2