[그리디] 1이 될 때까지 (파이썬)

어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다.

단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.

1. N에서 1을 뺀다.
2. N을 K로 나눈다.

수행해야 하는 최소 횟수를 구하시오.

---

#어떤 수 N이 1이 될 때까지
#1. N에서 1을 뺀다
#2. N을 K로 나눈다 (단, N%K == 0 일 때만)

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

# N이 K의 배수가 되게 맞추고
while n%k != 0:
  n = n - 1
  cnt +=1
  print(cnt, n)

#나눠줌
while n>1:
  n = n/k
  cnt += 1
  print(cnt,n)

print(cnt)

최소 횟수를 구해야 하는 것이기 때문에, 나누는 방법을 많이 사용하는 것이 좋다.

따라서, 1씩 빼며 나누는 방법을 사용할 수 있는 조건을 만들어 준 후에 나누는 방법을 사용하였다.