[그리디] 1이 될때까지

[내가 생각한 코드]

n, k = map(int, input().split())
count = 0
while True:
    if n%k:
        count+=1
        n=n-1
        if n==1:
            break
            
    else:
        count += 1
        n = n/k
        if n==1:
            break
            
    
print(count)

---

이 문제에 대한 해결방법은 N에 대하여 '최대한 많이 나누기'를 수행하면 된다. 나누는 것이 하상 더 숫자를 빠르게 줄이기 때문이다.

[단순하게 푸는 답안]

#1이 될때까지(책 풀이)
n, k = map(int, input().split())
result = 0

#N이 K이상이라면 K로 계속 나누기
while n >= k:
    #N이 K로 나누어 떨어지지 않는다면 N에서 1씩 뺴기
    while n % k != 0:
        n -= 1
        result +=1
    #K로 나누기
    n//=k
    result += 1

#마지막으로 남은 수에 대하여 1씩 빼기
while n>1:
    n -= 1
    result += 1

print(result)

[다른 답안]

#다른답안(책)
n, k = map(int, input().split())
result = 0

while True:
    #(N == K로 나누어떨어지는 수)가 될때까지 1씩 빼기
    target = (n//k)*k
    result += (n-target)
    n = target
    #N이 K보다 작을 때(더이상 나눌 수 없을 때) 반복문 탈출
    if n<k:
        break

    result += 1
    n//=k

result += (n-1)
print(result)

1. N이 K로 나누어떨어지는 수가 될때까지 1씩 뺸다
2. N이 K보다 작을때(더 이상 나눌 수 없을때) 반복문 탈출
3. 마지막으로 남은 수에 대하여 1씩 빼기..?