[코테 공부] 그리디 알고리즘(탐욕법 Greedy Algorithm)_2

현재 상황에서 지금 당장 좋은 것만 골라라!

실전 문제

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

• 방법
  1. N-1
  2. N/K

첫째 줄에 N(2이상 100,000이하), K(2이상 100,000이하)가 공백으로 구분되며 자연수이다. 이 때 N은 항상 K보다 크거나 같다.

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

입력 예시 :
25 5

출력 예시 :
2

문제 풀이

Tip

• N이 K의 배수가 될 때까지 1을 빼다가 (방법1)
• N을 K로 나눈다. (방법2)
  
  

#1이 될 때까지
import sys

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

# 입력 조건
if n not in range(2, 100000) or k not in range(2, 100000):
    print("Please enter a valid input")
    sys.exit() # 종료

while True:
    # N이 K로 나누어지지 않을 때는
    # 나누어지는 수가 될 때까지 1을 뺀다. (방법1)
    target = (n // k) * k
    result += n - target
    n = target

    # 더이상 나눌 수 없을 때 반복문 탈출
    if n < k:
        break

    # K로 나누기 (방법2)
    result += 1
    n //= k


# 계속 나누다보면 끝엔 결국 1이 남으므로 뺀다.
result += n - 1
print(result)