1이 될 때까지

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;


int main()
{
  freopen("input.txt","r",stdin);
  int n,k;
  int count=0;
  cin>>n>>k;

  while(true){
    if(n==1)
      break;
    if(n%k==0){
      n/=k;
      count++;
    }
    else{
      n-=1;
      count++;
    }
  }
  cout<<count;
}

문제 푸는 과정은 매우 매우 쉽다. 

일단 어떤 수 가 나오더라도, 1을 빼는 것 보다 k로 나누는 것이 더 빠르게 1로 갈 수 있으므로, k로 나누는 것을 중심으로 해결 한다. 만약 n이 k로 나누어 떨어지지 않을때는 n에서 1씩 빼가면서 n의 약수가 될 때 까지 뺀다.

나누어 지는 순간에 나누어 주면 된다.

각 순간 마다 count변수를 증가시켜주어 연산 횟수를 기록해준다.

모범 답안 코드는 다음과 같다. 나의 방식과는 조금 다르다.

#include <bits/stdc++.h>

using namespace std;

int n, k;
int result;

int main() {
    // N, K를 공백을 기준으로 구분하여 입력 받기
    cin >> n >> k;

    while (true) {
        // N이 K로 나누어 떨어지는 수가 될 때까지만 1씩 빼기
        int target = (n / k) * k;
        result += (n - target);
        n = target;
        // N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
        if (n < k) break;
        // K로 나누기
        result += 1;
        n /= k;
    }

    // 마지막으로 남은 수에 대하여 1씩 빼기
    result += (n - 1);
    cout << result << '\n';
}