[그리디]실전문제4. 1이 될 때까지

어떤 수 N이 1이 될 때까지 매번 아래 중 1개의 수행을 한다.
1. N에서 1을 빼기
2. N을 K로 나누기 (N이 K로 나눠질 때만 선택 가능)

N이 1이 될 때까지 둘 중 하나의 과정을 매번 수행해서 총 최소의 수행횟수를 구하는 문제이다.

일단 최소 횟수를 구하기 위해서는 나눗셈을 많이 사용하는 것이 좋다. 나눠질 때는 무조건 K로 나누도록 하고 이외에 상황에서 빼기를 수행하면 될 것 같다.

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

while (n != 1): #n이 1이 아닐 동안 계속 반복하기
  if (n % k == 0): #나눠떨어지면 나누고 카운트
    n = n / k
    count += 1
  else:
    n -= 1
    count += 1

print(count)

이렇게 풀었는데 교재에는 n>=k 일 때를 계산하고 끝난 후에 n>1동안 1씩 빼는 것으로 계산했다.

• 교재에 있는 새로운 풀이

while True:
	#n이 k로 나누어떨어지는 수가 될 때까지 1을 계속 뺀다.
    target = (n // k) * k
    result += (n - target)
    n = target
    if n < k:
    	break
    result += 1
    n //= k
   
result += (n-1)
print(result)