어떤수 n이 1이 될때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행
단, 두번째 연산은 n이 k로 나누어 떨어질 때만 선택가능
- n - 1
- n/k
n을 1로 만드는 최소 연산 횟수를 구하여라
=> 빼기보단 나누기가 훨씬 빠르게 차감되니 나누기가 메인이고 잔처리를 빼기로 해야된다.
1
2
3
4
5
6
7
8
9
10
11
n, k = map(int, input().split())
count = 0
while n != 1:
if n % k == 0:
n /= k
count += 1
n -= 1
count += 1
print(count)
문제에서는 N의 범위가 10만 이하로 설정되어있어서 하나씩 1을 빼는 작업이 그렇게 시간을 많이 잡아먹지 않지만, 100억이나 1000억 단위로 범위가 늘어나면 일일이 1씩 차감하는건 비효율적일 수 있다.
N을 엄청나게 큰 수로 가정했을 때, 빠르게 함수가 동작하게 하기 위해서는 N이 K의 배수가 되도록 효율적으로 한번에 빼는 방식으로 코드를 작성해야한다.
즉, 1을 하나씩 빼는게 아니라 한번에 차감해주는 방식으로 작성하겠다는 뜻이다.
이를 위해서는 나머지를 활용해야한다.
n이 k로 나누어 떨어지기 위해서는 n을 k로 나눈 나머지 만큼 빼주면 되기 때문이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n, k = map(int, input().split())
count = 0
while True:
residual = n%k
count += residual
n -= residual
if n < k:
break
count += 1
n //= k
count += (n-1)
print(count)
교재에서는 몫을 기준으로 했는데 내용은 아래와 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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)