[CodingTest] 1이 될 때까지

정재원·2021년 8월 28일

내 풀이

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

## 나눗셈은 빼기의 합이므로 나눌 수 있다면 나누는 게 좋다. (정당성 분석)

count = 0
while n != 1 :
  if n%k == 0:
    n /= k
    count += 1

  else :
    n -= 1
    count += 1

print(count)

정재원

생각합니다.

이전 포스트

[CodingTest] 두 배열의 원소 교체

다음 포스트

[CodingTest] 곱하기 혹은 더하기

1개의 댓글

정재원

2021년 8월 28일

아래의 모범답안은 내 풀이와 달리 시간 복잡도를 logn만큼만 걸리도록 작성되었다.

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

result = 0

while True:
  target = (n//k) * k
  result += (n-target)
  n = target
  if n < k :
    break
  result += 1
  n //= k

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

답글 달기