[이것이 취업을 위한 코딩테스트다] 그리디 알고리즘 - 1이 될 때까지

 

 

문제

 

어떠한 수 N이 1이 될 때 까지 다음의 두 과정 중 하나를 반복적으로 선택해 수행하려 함

단, 두번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있음

1. N에서 1을 뺀다.
2. N을 K로 나눈다.

N이 1이 될 때 까지 1번 혹은 2번의 과정을 수행해야하는 최소 횟수를 구하는 프로그램을 작성

 

 

나의 코드

# 정수 n과 k를 입력받는다.
n = int(input()) 
k = int(input()) 
count = 0

# n이 1보다 클 때까지 아래 조건문을 반복한다.
while n > 1:
    # n이 홀수이면 나눌 수 없으니 1을 뺀다.
    if n % k != 0:
      n -= 1
      count += 1

    # n이 짝수이면 k를 나눈다. 
    else: 
        n /= k
        count += 1

print(count)

# 정당성 분석: 아무리 큰 수가 입력되어도 1을 계속 빼서 1을 만드는 것보다 나누기를 이용해서 1을 만드는 것이 빠르기에 위 알고리즘은 정당하다.

 

해설 코드

# N, K공백을 기준으로 구분하여 입력 받기
n, k = map(int, input().split())

result = 0

while True:
    # N이 K로 나누어 떨어지는 수가 될 때까지만 1씩 빼기
    target = (n // k) * k
    result += (n - target)
    n = target
    # N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
    if n < k:
        break
    # K로 나누기
    result += 1
    n //= k

# 마지막으로 남은 수에 대하여 1씩 빼기
result += (n - 1)
print(result)