1이 될 때까지

풀이

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

while True:
    if m == 1:
        break
    if m % k == 0 or m > k:
        count += 1
        m = m // k
    else:
        count += 1
        m -= 1

print(count)

의도

빼거나 나누거나 둘 중에 하나를 선택해야 하는데 나눠지는 애들은 나눠 떨어지는 경우만 적용된다. 물론 문제 자체가 그리디 알고리즘이라는 큰 타이틀로 인해 그리디 방식으로 풀었지만 최대한 이득을 볼 수 있는 느낌은 알 수 있었다.

다른 풀이 1

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

while True:
    if m == 1:
        break
    if m % k == 0:
        m = m // k
    else:
        m -= 1
    count += 1

print(count)

정답인지 확인해보려고 다른 분들의 풀이를 좀 봤는데 내 코드의 중복을 찾을 수 있었다. 생각해보니 조건문의 or는 이미 첫번째 조건식으로 내포해버려서 제거해도 됐고 count += 1 코드 또한 분기 밖에 두면 뺄 수 있는 부분이었다.

다른 풀이 2

저녁에 정리 예정.