03 그리디 : 1이 될 때까지

어떠한 자연수 N이 1이 될때까지 두 과정중 하나를 반복적으로 수행하려고 한다. 단 두번째 연산은 N이 K로 나누어 떨어질때만 선택 할 수 있다. 

1. N에서 1을 뺀다.

2. N을 K로 나눈다.

예를 들어 N이 17, K가 4라고 가정하자. 이때 1번의 결과를 한번 수행하면 N은 16이 된다 이후 에 2번의 결과를 두번 수행하면 N은 1이 된다. 결과적으로 이 경우 전체과정을 실행한 횟수는 3이 된다. 이는 N을 1로 만드는 최소 횟수이다.

N과 K가 주어질 때 N이 1이 될때까지 1번 혹은 2번의 과정을 수행해야하는 최소 횟수를 구하여라

 

입력 조건

25 5

출력 조건 

2

 

풀이 코드 

#include <iostream>

using namespace std;

int main()
{
    int n, k;
    int result;
    cin >> n;
    cin >> k;
    
    for (n; n > 1; ) {
        if(!(n % k)) {
            n /= k;
        }
        else {
            n -= 1;
        }
        result++;
    }
    cout << result;
}