N의 값을 줄일 때 2이상의 수로 나누는 작업이 1을 빼는 작업보다 수를 훨씬 많이 줄일 수 있음
<문제> 1이 될 때까지: 정당성 분석
가능하면 최대한 많이 나누는 작업이 최적의 해를 항상 보장하는가?
N이 아무리 큰 수여도, K로 계속 나눈다면 기하 급수적으로 빠르게 줄임
다시 말해 K가 2 이상이기만 하면, K로 나누는 것이 1을 빼는 것보다 항상 빠르게 N을 줄일 수 있음.
또한 N은 항상 1에 도달하게 됨 (최적의 해 성립)
# <문제> 1이 될 때까지
#%%
n = 17
k = 4
while n != 1:
if n % k != 0:
n -= 1
n //= k
print(n)
#%% md
* 나는 이렇게 간단하게 풀었음
* 다른 숫자가 들어가면 무한 루프에 빠지게 됨... why?
#%%
n, k = map(int, input().split())
result = 0
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)
#%% md
* 정답 보고 나서 내 코드 버그 수정하기...
* 내 코드는 다시 1을 빼야 하는 순간에 돌아가지 못해서 에러가 발생했던 것임.
#%%
n, k = map(int, input().split())
result = 0
while n % k != 0:
n -= 1
print(n)
while n % k == 0:
n //= k
print(n)
#%% md
* 다시 뒤로 돌아가려면 어떻게 해야 하는가?
* 해답으로 돌아가보자
#%%
n, k = map(int, input().split()) # n = 25, k = 3이라고 가정
result = 0
while True:
# N이 K로 나누어 떨어지는 수가 될 때까지 빼기
# 먼저 정수 몫을 구한 다음에 다시 k를 곱한다 -> 몇 번 나눠 떨어질 수 있는지 구하기
# target = (25 // 3) * 3 = 24
# target = (8 // 3) * 3 = 6
# target = (2 // 3) * 3 = 0
target = (n // k) * k
# 그 다음에 n에서 target을 빼면 몇 번 뺴야 하는지가 나옴.
# result = 25 - 24 = 1
# result += 8 - 6 = 2 -> 2+2 = 4
# result += (2 - 0) -> 5+2 = 7
result += (n - target)
# n = 24
# n = 6
# n = 0
n = target
# N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
# 처음엔 n이 더 크다
# n 이 2이므로 while문 탈출
if n < k:
break
# K로 나누기
result += 1 # result = 2, 4+1 = 5
n //= k # 24 // 3 = 8, 6 // 3 = 2
# 마지막으로 남은 수에 대해서 1씩 빼기
# result += (7 - 1) -> 6
result += (n - 1)
print(result)
#%% md
* 로그 시간 복잡도로 문제를 풀기 위해서 위와 같은 코드를 가져옴
* 일일이 n과 k를 확인한 다음에 문제를 풀어도 되지만, 그렇게 되면 시간 복잡도가 늘어남.