t_1이될때까지_99

source	github.com/ndb796/python-for-coding-test
topics	600-알고리즘 & 코딩테스트 602 그리디
types	문제풀이

문제

n이 1이 되야함 아래의 과정을 통해..

N -1을한다
N/k를 한다(나누어떨어질때만 가능)

답

나누는게 더 극단적이니 나누는것 > 빼는것을 고려해볼듯하다.
N-1이니 나누는것보다 N-1이 더 빠를 가능성은 없다
그리고 N/k의 값은 N-1로도 모두 구현이 가능하다.
THEREFORE GREEDY

import sys
n,m = map(int, sys.stdin.readline().split())

cnt = 0
while n>1:
    tmp =  n%m 
    if tmp == 0:
        n //= m
        cnt += 1
    else:
        n -= tmp
        cnt += tmp

print(cnt)