그리디 알고리즘 & 구현 1

문제를 해결할 때 값이 k로 나누어 떨어지면 나눗셈을, 그렇지 않으면 -1을 수행하여 최소한의 횟수로 1에 도달하게 구현하였다.

---소스코드---

#두 입력이 주어지면 n이

#n,k을 공백을 기준으로 구분하여 입력받기

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

result = 0

while True:
    #n이 k로 나누어 떨어지는 수가 될때까지 빼기
    target = (n//k)*k
    result += (n-target) # result에 나누어 떨어질때까지 뺀 수 더하기
    n = target      #n에 빼고 가장 가까운 나누어 떨어지는 수 저장

    if n<k:
        break       #나눌 수보다 작아진다면 포문 탈출

    result+=1       #나눗셈 했으니 1번 카운트 하기
    n //=k      #다음 수까지 나눠주기

result+=(n-1)   #마지막 남은수 만큼 뺀 만큼 카운트해주기
print(result)