이것이취업을위한코딩테스트다ch03그리디_3-6 1이 될 때까지.py

문제 설명

N이 1이 될 때까지 다음의 두 과정 중 하나를 선택하여 반복 수행하는 최소 횟수를 구하라.
1. N에서 1을 뺀다.
2. N이 K로 나누어 떨어지면 N을 K로 나눈다.

ex) N = 17, K = 4.
1번 과정을 한 번 수행하면 N = 16이 된다. 이후에 2번 과정을 두 번 수행하면 N은 1이 된다. 전체 과정을 실행한 횟수는 3으로 최소 횟수가 된다.

문제 해결 아이디어

주어진 N에 대해여 최대한 많이 나누기를 수행하면 된다.
반복을 주어진 N에 대해서 진행하는 것이 아니라 K로 나누어 떨어지는 숫자를 만들고 나누는 것을 반복한다.
1. K로 나누어 떨어지는 N을 만들자.
target = (n//k) * k
2. target(k로 나누어 떨어지는 수)를 N으로 만들기 위해서 그만큼 빼기 과정을 진행해야 한다.
result += (n - target)
3. 뺴기 과정을 진행했기 때문에 n은 target이 된다
n = target
4. 이 반복을 탈출하는 조건은 n < k 이라서 나누어지지 않을 떄.
if n < k : break 탈출 후, result += (n - 1) 을 통해서 n이 1인 상태가 되도록 뺴기를 하면 마무리한다.

n, k = map(int, input().split())
result = 0
while True :
  # 나눠서 나머지가 없는 값으로 target을 만든다. 
  # n // k를 통해서 몫을 구하고 k를 곱하면 나눠어 떨어지는 값이 된다
  # target은 그냥 temp 변수
  target = (n//k) * k
  # 나머지값을 result에 넣기
  result += (n-target)
  n = target
  # n이 k보다 작을 때(즉, 이상 나눌 수 없을 때) 반복문 탈출
  if n < k:
    break
  result += 1
  n //= k

result += (n-1)
print(result)