[이.코.테] 그리디 (3) -- 1이 될 때까지

 

 

# N이 1이 될 떄까지 1 혹은 2 과정을 수행해야 하는 횟수의 최솟값
# 1) N-1
# 2) N/K -- N이 K로 나누어떨어질 떄에만 선택 가능

def until_one():
    n, k = map(int, input("25 5 --").split())
    result = 0
    while n != 1:
        if n % k == 0:
            n /= k
        else:
            n -= 1
        result += 1
    return result

print(until_one())

'''
# K로 가능한 한 많이 나눴을 때 가장 빠르게 N=1 만들 수 있다.
# N이 K의 배수가 되도록 효율적으로 한 번에 빼는 방식

# N, K를 공백으로 구분하여 입력받기
n, k = map(int, input("25 5 --").split())
result = 0

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

# 마지막으로 남은 수에 대하여 1씩 빼기
result += (n - 1)   # 3-1
print(result)       # 2
'''