2-3. 이코테 - Greedy - 1이 될 때까지

• 링크 : https://www.youtube.com/watch?v=2zjoKjt97vQ&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=2&t=2572s

''' 내가 푼 - 간단 '''
def sol(n, k):
    answer = 0
    
    while n != 1:
        if n % k == 0:     # n을 k로 나눌 수 있다면
            n /= k
            answer += 1
        else:             # 나눌 수 없다면
            n -= 1
            answer +=1
    
    return answer

print(sol(25, 5))
print(sol(25, 3))
print(sol(17, 4))

''' 동빈나 해설코드 '''
def sol(n, k):
    answer = 0
    
    while 1:
        # 먼저 N이 K로 나누어 떨어질 수 있을 때까지 -1 해준다 (곱으로)
        target = (n//k) * k
        answer += (n - target)
        n = target
        
        # 이때, 더이상 나눌 수 없는 값이 되어버리면 반복문 탈출
        if n < k:
            break
        
        # 충분히 빼줘서 나눌 수 있어졌다면 K로 나누기 (= +1회)
        n //= k
        answer += 1
    
    # 마지막으로 수가 남았다면 1씩 빼기
    answer += (n-1)
    return answer


print(sol(25, 5))
print(sol(25, 3))
print(sol(17, 4))