1. 그리디 알고리즘

그리디 알고리즘의 대표적인 문제인 '거스름돈 문제'에서 그리디 알고리즘이 최적의 해를 구할 수 있었던 이유는 큰 수가 작은 수의 배수이기 때문이다. (500원은 100원의 배수)

이렇듯 그리디 알고리즘 문제가 나왔을 때는 그리디 기법이 최적의 해를 구할 수 있는지에 대해 검토해야 한다.

2. 문제 설명

3. 문제 검토

K는 고정이 되어 있고 큰 수에서 나누는 것이 가장 최적의 해를 구할 수 있는 방법이기 때문에 이 문제는 그리디 기법이 알맞은 기법이 되겠다.

중요한 것은 매 수행마다 1로 빼는 것보다 1보다 큰 K로 N을 나누는 것이 1에 훨씬 더 빠르게 도달할 수 있는 방법이다.

4. 풀이

from sys import stdin

N,K = map(int,stdin.readline().split())

cnt=0

while(True):
    if N==1:
        break
    elif N % K == 0:
        N/=K
    else:
        N-=1
        
    cnt+=1
    
print(cnt)
    

주어진 조건만 구현하면 된다.

5. 총평

매우 쉬운 문제이다.
허나 문제의 최적의 해를 그리디 기법으로 구할 수 있는지에 대한 검토 능력을 기를 수 있는 아주 좋은 예시이다.