[그리디] 04. 1이 될 때까지

<이것이 취업을 위한 코딩테스트다 with 파이썬> 책의 예제 문제에 대한 제 답안을 작성한 게시글 입니다.

CHATER 03 그리디

P.99

내 코드

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

result = 0

while True:
    if n % k == 0:
        n = n // k
        result += 1
    else:
        n -= 1
        result += 1

    if n == 1:
        break

print(result)

하지만 이는 n의 값이 커지면 1을 빼는 연산에서 시간이 걸리므로, 다음과 같이 연산을 개선할 수 있다.

 

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

result = 0

while True:
    target = (n // k) * k
    # k로 나누어떨어질 수 있을 때까지 1을 뺀다.
    result += n - target
    n = target
    # n을 더이상 k로 나눌 수 없는 경우
    if n < k:
        break
    # n을 k로 나누기
    n //= k
    result += 1

# 남은 수들 1만큼 빼기
result += n - 1

print(result)