Python - 그리디 알고리즘 - 1이 될 때까지

728x90

# 그리디 알고리즘
# 1이 될 때까지

# 어떠한 수 N이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다.
# 단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.

# 1. N에서 1을 뺀다.
# 2. N을 K로 나눈다.
# N이 17, K가 4라고 가정, 1번 과정 거치면 N을 16, 이후 2번의 과정 거치면 N은 1

# n, k입력받기

n, k = map(int, input().split())
result = 0 # 몇번인지 체크

while n >= k: # n이 k보다 크거나 작을때까지 = n이 k로 나누어지기 전까지
    while n % k != 0: # n이 k로 나누어지기 전까지
        n -= 1
        result += 1
    
    n /= k
    result += 1
    
if n > 1:
    n -=1
    result += 1
    
print(result)

책 참고

# 책 참고

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

while True:
    target = (n//k) * k # n//k = 몫 * k , 25//3 = 8 * 3, 8 //3 = 2*3, 2//3 = 0 *k
    result += (n-target) 
    n = target # 25 = 24로 변경, 6, 2
    
    if n < k: # 2는 3보다 작으니 break
        break
    
    # k로 나누기
    result += 1
    n //= k # 24 //3 = 8, 6 //3 = 2
    


result += (n-1)
print(result)

728x90