1이 될 때까지 반복적으로 수행

1. 문제 설명

출처 : 이코테 2021

2. 문제 해결 아이디어

• 주어진 N에 대하여 최대한 많이 나누기를 수행
• N의 값을 줄일 때 2이상의 수로 나누는 작업이 1을 빼는 작업보다 수를 훨씬 많이 줄일 수 있다.
• N = 25, k = 3일경우

 

3. 정당성 분석

• N이 아무리 큰 수여도, k로 계속 나눈다면 기하급수적으로 빠르게 줄일 수 있다.
• 항상 1에 도달하게 된다. (최적의 해 성립)

 

4. 코드

#N, K을 공백으로 기준으로 구분하여 입력
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

# 마지막으로 남은 수에 대하여 1씩 빼기
result += (N-1)
print(result)

target = k로 나누어 떨어지는 수이며 result는 연산의 횟수이다.

코테 조건에서 n과 k의 값이 10만이하라고 정의되어 있는데 그럴경우는 하나하나 n값을 비교해서 구할 수 있다.

하지만 while문을 사용한다면 n과 k의 범위가 매우 커져도 시간복잡도가 기하급수적으로 나눠지기 때문에 효울적인 알고리즘을 구현할 수 있다.