[그리디 / python] 1이 될 때까지

✔️ 문제풀이 1

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

while n>=k:
    while n%k!=0:
        n-=1
        cnt+=1
    n//=k
    cnt+=1

while n>1:
    n-=1
    cnt+=1

print(cnt)

 

1. n이 k 이상이면 k로 계속 나누기

2. n이 k의 배수가 아니면(n%k!=0이면) 1씩 빼기

3. n이 k의 배수가 되면 k로 나누기

 

4. 위 반복을 거친 후 마지막으로 남은 수 1씩 빼기(n>1 일 때까지!)