그리디 : 1이 될 때 까지

📈금융 개발 블로그 : https://quantpro.co.kr/

어떤 수 N이 1이 될 때까지 특정 연산하는 횟수를 구하는 문제

📌 문제 설명

1. n이 1이 될 때까지 아래의 두 방법을자유롭게 이용할 수 있다.

2. 단 두번 째 연산은 N이 K로 떨어 질때만 할 수 있다.
   방법1 : N에서 1을 뺀다
   방법2 : N을 K로 나눈다

3. N과 K가 주어질 때 N이 1이 될 때 까지 1번 혹은 2번의 과정을 수행해야 하는 최소회수를 구하기

🥕입력예시

25 5

🥕출력예시

2

📌 문제 풀이

1로 만드는 최소횟수를 구해야 하므로 숫자를 작게 만드는 것에 초점을 맞추어야한다. 따라서 최대한 많이 나누는 것에 초점을 맞추면 된다. k로 n을 계속 나누며 나누어 지지 않을 때는 n이 k의 배수가 될 때까지 빼면 된다.

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

result = 0

while True:
  #나누어 지는 수로 만들기
  target = (n//k)*k
  result += (n-target)
  n = target
  # 더이상 못나눌 때 종료
  if n<k:
    break
  #k로 만들기
  result += 1
  n//=k

#1만 남기고 빼는 횟수
result += (n-1)```