[이코테] CH03 그리디 실전문제 1이 될 때 까지

from collections import deque
sys.setrecursionlimit(100000000)
import heapq
INF = 1e9

N,K = map(int,sys.stdin.readline().split())
count = 0
while True:
    if N == 1:
        break
    if N%K == 0:
        N = N / K
        count +=1
    else:
        N -=1
        count +=1

print(count)

일단 이게 내 코드이다

K가 2보다 크거나 같다는 것을 보고

K로 나눠줄 수 있으면 무조건 나눠주는 것이 이득이겠구나를 잡아내고

간단하게 풀었다

테스트 케이스도 다 맞는 건 확인했지만

반례가 있다면 환영입니다 ! 

이건 답안입니다

 

import sys
# sys.stdin.readline()
from collections import deque
sys.setrecursionlimit(100000000)
import heapq
INF = 1e9

N,K = map(int,sys.stdin.readline().split())
sum = 0
while N>=K:
    while N%K!=0:
        N-=1
        sum +=1
    N //=K
    sum +=1

while N>1:
    N-=1
    sum +=1

print(sum)