그리디 1-4) 1이 될 때까지

문제

어떠한 수 N이 1이 될 때까지 아래 두 과정중 하나를 반복적으로 수행한다. 단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.

1. N에서 1을 뺀다.
2. N을 K로 나눈다.

N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야하는 최소 횟수를 구하는 프로그램을 작성하시오.

입력조건

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

출력조건

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

문제해설

주어진 N에 대하여 '최대한 많이 나누기'를 수행하면 된다. 왜냐하면 어떠한 수가 있을 때, '2 이상의 수로 나누는 것'이 '1을 빼는 것'보다 숫자를 훨씬 많이 줄일 수 있기 때문이다.

예를 들어 N=25, K=3일 때는 다음과 같다.

# 1이 될때 까지
def Num1(n, k):
    result = 0
    while True:
        if n == 1:
            break
        elif n % k == 0 :
            n /= k
        else:
            n -= 1
        result += 1
    return result
print(Num1(25, 5))

* input 계속 입력하기 귀찮아서 함수형태로 코드 작성