[이코테] 1이 될 때까지 / 파이썬 / python / 그리디

👩🏻‍💻 code

import sys
sys.stdin = open("input.txt","rt")
input = sys.stdin.readline
n,k=map(int,input().split())

count=0

while True: # k로 최대한 많이 나눠야함!
    tmp=(n//k)*k 
    count+=n-tmp # k배수로 만들고 남은만큼 다 1씩 빼기,
    n=tmp # n은 k배수로 갱신

    if n<k: # n이 k보다 작아져 더 나눌수 없음
        break
    
    n=n//k # k배수가 된 n을 k로 나눈 몫으로 갱신
    count+=1 # k로 나눠 줬으니까 +1 해줌

count+=n-1 # k로 못 나누고 남은 만큼 다 1씩 빼기.
print(count)

---

🌈 해설

1씩 빼는 거 보다 나누기를 많이 해야 숫자가 빨리 줄어든다!
n을 k로 많이 나눌 수 있도록  n을 k의 배수로 만들어준다.

자세한 설명은 주석!