문제2) 1이 될 때까지

문제 2: 1이 될 때까지

어떠한 수 N이 1일 될때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 합니다.

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

1. N에서 1을 뺍니다.

2. N을 K로 나눕니다.

 

예를 들어, N이 17, K가 4라고 가정합시다. 이때 1번의 과정을 한번 수행하면 N은 16이 됩니다.

이후에 2번의 과정을 두 번 수행하면 N은 1이 됩니다.

결과적으로 이 경우 전체 과정을 실행한 횟수는 3이 됩니다.

이는 N을 1로 만드는 최소횟수입니다.

 

N과 K가 주어질 때, N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는

최소 횟수를 구하는 프로그램을 작성하세요

 

---

 

 

내가 작성한 코드

N, K = map(int, input().split())
count = 0

# 알고리즘 측정시간
import time
start_time = time.time() # 측정 시작

while N != 1:
    if N % K == 0:
        count = count + 1
        N = N // K
    elif N % K != 0:
        count = count + 1
        N = N - 1

print(count)

# 프로그램 소스코드
end_time = time.time() # 측정 종료
print('---- %f seconds(time) ----' % (end_time - start_time)) # 수행 시간 출력


# input & output
# 100000 3
# 19
# ---- 0.000063 seconds(time) ----

 

---

 

나동빈님 코드

이번에는 간결하다는 느낌보다는 논리적으로 코드를 작성한게 놀라웠다. 

target이랑 result 변수를 설정하는 부분이 특히 그렇다.

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

result = 0

# 알고리즘 측정시간
import time
start_time = time.time() # 측정 시작

while True:
    # N이 K로 나누어 떨어지는 수가 될 때까지 빼기
    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)

# 프로그램 소스코드
end_time = time.time() # 측정 종료
print('---- %f seconds(time) ----' % (end_time - start_time)) # 수행 시간 출력

# input % ouput
# 100000 3
# 19
# ---- 0.000076 seconds(time) ----

 

 

---

컴파일러가 런타임은 내가 작성한게 더 빠르다는 결과가 냈는데, 조작한거 아니다.