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

교재 : 이것이 코딩 테스트다 with 파이썬
Chapter 03. 그리디
실전문제 04. 1이 될 때까지

문제

두 숫자 N과 K가 입력으로 들어오면 N이 1이 될 때까지 아래의 2가지 연산중 한가지를 수행한다. N을 1로 만드는 연산의 최소 횟수를 구한다.
2가지 연산: 1) N에서 1을 뺀다. 2) N을 K로 나눈다.

입력
자연수 N, K

출력
N을 1로 만드는 연산의 최소 횟수

풀이

N이 K로 나누어 떨어지면 N/K, 나누어 떨어지지 않으면 N-1을 수행

# 1이 될 때까지

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

# n/k를 많이 수행해야 총 연산횟수를 줄일 수 있음
# n이 k로 나누어 떨어지면 n/k, 나누어 떨어지지 않으면 n-1
while(n > 1):
    if (n%k == 0):
        n = n/k
        count +=1
        print("나누기")
    else:
        n -= 1
        count += 1
        print("빼기")
print(count)

References
이것이 코딩 테스트다 with 파이썬 - 나동빈 저