[이것이 코딩테스트다] - 그리디

실전문제: 1이 될 때까지

 

내가 쓴 답안

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

result=0

 

if n%k==0:

  while n!=1:

    n=n//k

    result+=1

elif n%k!=0:

  while n%k!=0:

    n=n-1

    result+=1

  while n!=1:

    n=n/k

    result+=1

print(result)

 

생각 과정

#1)만약 나누어지는 경우라면 N을 K로 나눈다. 1이 될 때 까지

#2)안 나눠지는 경우라면 N에서 1을 뺀다.

#ex 18에 4면 17 4 16 4

 

중간에 잘못 생각한 부분: WHILE N/K!=1이 아님

핵심: k가 2 이상이기만 하면 k로 나누는 것이 1을 빼는 것보다 항상 빠르게 n의 값을 줄일 수 있음

그러므로 k로 최대한 많이 나눌 수 있도록 최적의 해 보장하기