[그리디] 1만들기 예제

예제

1이 될 때까지

📌 거스름돈이 배수 관계이기 때문에 최적의 해 보장 -> 그리디 사용

문제

어떠한 수 n이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다.
단, 두 번째 연산은 n이 k로 나누어떨어질 때만 선택할 수 있다.

• n에서 1을 뺀다.
• n을 k로 나눈다.
  n과 k가 주어질 때, n이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구해라.

⌨️ 코드

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

while True:
    target = (n//k)*k #나누어 떨어지는 가장 가까운 수
    result += (n - target) #나머지 (1빼기 횟수)
    n = target
    
    if n<k: #더이상 나눌 수 없을 때
        break
    #k로 나누기
    result += 1
    n //= k
    
result += (n-1)
print(result)

---