•
나의 풀이
결과(result) 횟수만큼 연산하기 때문에, 복잡도가 가 된다.
a, b = map(int, input().split())
result = 0
while a != 1:
# 1번과정
if a % b == 0: a //= b
# 2번과정
else: a -= 1
result += 1
print(result)
Python
복사
•
강의 풀이
나눗셈으로 최대한 많이 숫자를 줄인 후, -1 연산 [ 1번연산 ]의 횟수만 확인하는 방식
결과(result) 횟수만큼 매번 연산하지 않고, 계속 n을 나눠주기 때문에 복잡도가 으로 된다.
n, k = map(int, input().split())
result = 0
while True:
# n에서 나머지가 존재하지 않는 가장 가까운 수 구하기
taeget = (n // k) * k
# 해당 수(target)과 n과의 수 차이를 result에 반영
# 이 과정에서 (-1을 하는 연산과정)[1번 연산] 갯수를 result에 더한다.
# 예) n = 25, target = 21 일 때, n이 나누는 연산[2번 연산] 을 진행하기 위해서는 총 4번의 [1번연산]이 필요
result += (n - taeget)
# [1번 연산]이 필요 없는 값을 n에 적용
n = taeget
# 만약 나눌 수 없는 경우 나누지 않고 멈춤
if n < k:
break
# n을 나눈다. [2번 연산]
n //= k
# 2번 연산 1번 진행 추가
result += 1
# 나눌 수 없다면, 이제는 [1번 연산]만 가능하기 때문에, result에 n을 더하지만
# 그렇다면 n이 1까지 연산하는 갯수가 아닌, 0까지 되는 연산 횟수기 때문에 1은 빼준다.
result += (n-1)
Python
복사