그리디(탐욕법) 알고리즘 - 1이 될 때 까지

문제 설명

어떠한 수 N이 1이 될 때 까지 다음 두 과정 중 하나를 반복 선택 수행하려고 한다. 단, 두번째 연산은 N이 K로  나누어 떨어질 때만 선택할 수 있다. 1. N에서 1을 뺀다. 2. N을 K로 나눈다. 이때의 최소 수행 횟수를 구하기

 

풀이 1 : 긴시간이 걸림.  O(N)의 시간 복잡도

count=0
def solution(k,n):
    global count
    while(n>=2):
        if n%k==0:
            n/=k
        else : n-=1
        count+=1 
    print(count)
solution(17,4)

 

풀이 2: 짧은 시간이 걸림 .  O(logN)의 시간 복잡도

 

count=0
def solution(k,n):
    global count
    while True:
    # N이 K로 나누어 떨어지는 수가 될 때 까지 빼기
        target = (n//k)*k
        count += (n-target)
        n = target
    # N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
        if n<k: break
    
        count+=1
        n//=k
    
    #마지막으로 남은 수에 대해 1씩 빼기
    count += (n-1)
    print(count)
    
solution(17,4)