[그리디 알고리즘] 1이 될 때까지 ★☆☆

---

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

• N에서 1을 뺀다
• N을 K로 나눈다 (K로 나누어지는 경우)

위 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하라

 

입력 조건

• 조건 1 : 첫째 줄에 N(2<=N<=100000)과 K(2<=K<=100000)가 공백으로 구분되어 주어진다
• 조건 2 : N은 K보다 크거나 같다 

출력 조건

• 조건 1 : 첫째 줄에 N이 1이 될 때까지 수행해야 하는 과정의 최솟값을 출력한다

 

입력 예시

25 5

출력 예시

2

---

해결 방법을 한 문장으로 나타내면 "나눌 수 있으면 항상 나눈다" 이다

코드 또한 매우 간단하다

---

#include<bits/stdc++.h>
using namespace std;
int n, k;
int ans;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    while (n!=1) {
        if (n % k == 0) n /= k;
        else n--;
        ans++;
    }
    cout << ans;
    return 0;
}