<CodingStudy>Greedy3

이것이 코딩테스트다 1이 될때까지 실전 문제

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

1.N에서 1을 뺀다.

2.N을 K로 나눈다.

두번째 연산은 N이 K로 나누어떨어질 때문 선택할 수 있다.

 

입력조건 :

첫째 줄에 N(2<=N<=100,000)과 K(2<=K<=100,000)가 공백으로 구분되며 각각 자연수로 주어진다. 이때 입력으로 주어지는 N은 항상 K보다 크거나 같다.

 

출력 조건 :

첫째 줄에 N이 1이 될때까지 1번 혹은 2번 의 과정을 수행해야 하는 횟수의 최솟값을 출력한다.

 

입력예시 :

25 5

 

출력 예시:

2

 

#include <iostream>
using namespace std;
int main()
{
    
    int n, k;
    cin >> n >> k; //n 과 k 가 공백을 두고 입력을 받고
    int result = 0;//결과를 위해 선언 
    
    while (n!=1)//n이 1이될때까지 무한반복 
    {
        if (n % k == 0) // n/k로 나눠지면 나머지는 0 이기 때문에 true 이면 
        {
            n=n / k; // n/k
            result++; // result 1 증가
        }
        else//안 나눠지면 
        {
            --n; // n 1감소
            result ++; // result 1 증가 
        }
        
        
    }
    cout << result;//결과
}

출력 1

출력2

 

 

출력 1는 5로 2번 나눠지기때문에 결과값 2

출력 2는 17-1 1번 16을 4로 2번 나눠서 결과값 3