• 이번에 다루어볼 그리디 알고리즘의 문제는 2018 E 기업 알고리즘 대회에서 나온 문제이다. 당분간, 그리디의 유형에서 '구현' 알고리즘의 문제를 공부할 것으로 알고리즘 공부가 전체적으로 끝나면 다시 그리디 알고리즘으로 돌아와서 머리 쓰는 연습을 하도록 하겠다. 그럼 마지막 문제를 시작해보겠다.

문제 : 1이 될 때까지

1. 문제설명

• 입력조건

  첫째 줄에 N(2 <= N <= 100,000)과 K(2 <= K <= 100,000)가 공백으로 구분되며 각각 자연수로 주어진다. 이때 입력으로 주어지는 N은 항상 K보다 크거나 같다.

• 출력조건

  첫째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최솟값을 출력한다.

2. 문제 풀이
   위 문제의 해결 point는 '최대한 많이 나누기' 이다. 우리는 쉽게 입력받은 숫자를 1로 만들기 위해서는 '1로 하나씩 빼기' 의 계산보다 '2이상의 수로 나누기'가 더 숫자를 빠르게 줄일 수 있다는 생각을 할 수 있다.
   (1) 단순하게 푸는 답안

• N이 K이상일 때는 나누어 떨어지지 않는다면 1을 빼고, 그 외는 K로 나누어 계산한다.
• N이 K보다 작을 때는 더 이상 나누어 떨어질 수 없으므로 1씩 뺀다.

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

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

n //= k
sum += 1

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

print(sum)

(2) 다음 방법은 N이 범위가 100억 이상의 큰 수가 되었을 때를 가정해서 빨리 푸는 방법을 나타낸다. 위 유형은 N이 K의 배수가 되어 나누는 연산을 한번에 하도록 한다. 즉, 1을 빼는 계산을 앞에서 다 수행하면서 N을 K의 배수로 만든 후 연산을 진행하는 방법이다. 위 코드는 다음과 같다.

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

while True:
target = (n // k) * k
result += (n - target)
n = target

if n < k:
    break
result += 1
n //= k

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