greedy 알고리즘

탐욕적으로 현재 상황에서 가장 최적의 문제풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토한다.

문제

1이 될 때 까지, N을 K로 나누거나 N에 1을 빼거나 행동의 최소 횟수 구하기

조건

N(1 <= N <= 100,000) K(2 <= K <= 100,000)

풀이

K가 2이상이므로 1을 빼는 것보다 최대한 많이 나누는 것이 연산횟수를 최소화할 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
N,K = list(map(int,input().split(' ')))
count = 0

# 시간복잡도 O(N)
while N != 1:
    if (N % K == 0):
        N /= K
        count += 1
        continue
    N -= 1
    count += 1

# 시간복잡도 O(log N)
while True:
    target = (N // K) \* K
    count += (N - target)
    N = target
    if N < K:
        break
    count += 1
    N //= K

count += (N - 1)
print(count)