[그리디 알고리즘] 문제1 - 1이 될 때까지

1이 될 때까지

1) 문제 해결 아이디어

N에 대해 최대한 많이 나누기(2번 연산)을 수행

N의 값을 줄 일 때, 2 이상의 수로 나누는 작업이 1을 빼는 작업보다 수를 훨씬 많이 줄일 수 있음

 

2) 정당성 분석

Q. 가능하면 최대한 많이 나누는 작업이 최적의 해를 항상 보장할 수 있는가?

K가 2 이상이면 K로 나누는 것이 1을 빼는 것보다 항상 N을 빠르게 줄일 수 있음

 

3) 소스코드

n, k = map(int, input().split())
count = 0  # 최소 횟수

while True:
  # 탈출 조건
  if(n == 1):
    break
  # n이 k로 나누어 떨어지면 나누기
  if(n % k == 0):  
    n /= k
  # n이 k로 나누어 떨어지지 않으면 빼기
  else:
    n -= 1
  count += 1

print(count)