문제

첫째 줄에 N(1 이상 100,000 이하), K(2이상 100,000이하)가 공백을 기준으로 하여 각각 자연수로 주어진다.
첫째 줄에 N이 1이 될 때까지 1번(1 빼기) 혹은 2번(K로 나누기)의 과정을 수행햐야 하는 횟수의 최솟값을 출력합니다.

입출력 예시

25 5 -> 2
25 3 -> 6

해설

N에 대하여 최대한 많이 나누기를 수행하면 된다.
왜냐? 1을 일일이 빼는 작업보다 2 이상의 수로 나누는 작업이 수를 훨씬 빨리 줄일 수 있음
그리고 N은 항상 1에 도달할 수 있음(최적의 해 성립)

내 코드

import sys
N, K = map(int, sys.stdin.readline().split())

count = 0 #연산횟수 
while N>1: #N이 1보다 클 때만 연산 가능
    # print("현재 숫자:", N,"현재 횟수:", count)
    if N%K==0:
        count += 1
        N //= K
    else:
        N -= 1
        count +=1

print(count)

이코테 코드

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

result = 0

while True:
    # N이 K로 나누어 떨어지는 수가 될 때까지 빼기
    target = (n//k)*k #예를 들어 15를 2로 나누면 몫은 7이다. 그렇다면 2로 나눠지는 가장 가까운 수는 7*2=14이다.
    result += (n-target) #1을 빼는 연산을 몇 번 수행할지 계산해서 넣음
    n = target # n은 target으로 변경되어 나누기를 할 준비를 한다.
    # N이 K보다 작아 나눌 수 없을 때 반복문 탈출
    if n<k :
        break
    # K로 나누기
    result +=1
    n //= k

# 마지막으로 남은 수에 대해 1씩 빼기
# 예를 들어 k는 5인데 4가 남았으면 1 빼기를 3번 해야한다.
result += (n-1)
print(result)

이 방법은 반복문이 한 번 실행될 때마다 무조건 n으로 나누기 때문에 반복 횟수에 따라 n이 빠르게 줄어들 수 있음. n과 k에 아무리 큰 수가 와도 로그 시간 안에 해결 가능