1이 될때까지 최소 연산 횟수

 

n과 k 라는 자연수가 주어진다고 하면  아래 두가지 연산 중 하나씩 진행하여 n이 1이 되도록 하는데

연산 횟수를 최소화 하는 알고리즘을 작성하라.

 

1. n 에서 1을 빼기

2. n 에서 k를 나누기

 

이런 문제가 있다고 하자.

 

이 문제는 그리디 알고리즘의 유명한 문제다.

 

해설을 보기전 나의 경우는

 

n = 25
k = 5
count = 0

while 1 : 

  if n%k ==0:
    n=n/k
    count+=1
  else :
    count+=1
    n= n-1  

  if n==1 :
    break

print(count)

이런 식으로 풀었다. 이 방법도 틀린 방법은 아니지만 주어지는 숫자의 범위가 커지면 문제가 생길 수 있다.

 

그래서 사용하는 테크닉이 해설 코드에 있었다.

 

 

n = 17
k = 4
count = 0

while 1 : 
  # N이 K로 나누어 떨어지는 수가 될 때까지 뺴기
  target = (n//k)*k
  count += (n-target)
  n = target
  # N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
  if n<k:
    break
  # K로 나누기
  count +=1
  n//=k
# 마지막으로 남ㅇ느 수에 대하여 1씩 빼기
count += (n-1)

print(count)

  target = (n//k)*k
  count += (n-target)

이 부분이 핵심인데 첫번째 줄 코드를 실행하면 "n이 k와 나누어 떨어지는  숫자중 현재 n과 가장 큰접한 숫자" 를

구할 수 있게 된다.