[2018 E 기업 알고리즘 대회 | 그리디 문제풀이] 1이 될 때까지

어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 

합니다. 단, 두번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있습니다.

N에서 1을 뺍니다.
N을 K로 나눕니다.
예를 들어 N이 17, K가 4라고 가정합시다. 이 때 1번의 과정을 한 번 수행하면 N은 16이 됩니다. 

이후에 2번의 과정을 두번 수행하면 N은 1이 됩니다. 결과적으로 이 경우 전체 과정을 실행한 

횟수는 3이 됩니다. 이는 N을 1로 만드는 최소 횟수입니다.

N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 

최소 횟수를 구하는 프로그램을 작성하세요.

 

<입력 조건>

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

<입력 예시>

25

<출력 예시>

2

 

input = [25,3]
let N = input[0]
let K = input[1]
let count = 0; 

while(N>1){
    if(N%K===0){
        N /= K
    }else N-=1
    count+=1
}
console.log(count)

역시 동일한 힌트가 존재한다. 1번 혹은 2번 과정을 수행하는 최소 횟수는 

1을 빼는 것보다 N을 나누는 것이 수가 무조건 더 작아진다. 

N은 1보다 큰 수인 2부터 시작되기 때문이다. 

 

힌트는 곧, 1을 빼는 것보다 큰 수로 나누는 것을 반복하는 것을 먼저 실행하는 것이다. 

그래서 나누어 떨어지면 나누고, 그렇지 않으면 1을 빼는 작업을 반복하며,

반복할 때마다 카운트에 값을 누적했다.