△ - [ 그리디 ] 1이 될 때까지 - R

난이도 : 하  풀이시간 : 30/3  시간제한 : 1초 

[ 그리디 ] 1이 될 때까지

 

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

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

1. N에서 1을 뺀다.
2. N을 K로 나눈다.

N이 1이 될 때 까지 1번 혹은 2번의 과정을 수행해야하는 최소 횟수를 구하는 프로그램을 작성하시오.

 

:: 입력 조건

 

첫째 줄에 N(2<= N <= 100000)과 K(2 <= K <= 100000)가 공백으로 구분되며 각각 자연수로 주어짐

이때, 입력으로 주어지는 N은 항상 K보다 크거나 같음

 

:: 출력 조건

 

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

 

 

---

  아이디어  

1. n, k 입력받기

2. n이 1이 될때까지 while ( n이 k의 배수라면 나누고 아닐 경우에 1을 뺌 )

3. while문이 도는 횟수를 체크해서 출력

 

  내   코드  

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int main() {
	int n, k;
	cin >> n >> k;

	int cnt = 0;

	while (n != 1) {
		if (n % k == 0) {
			n /= k;
		}
		else n -= 1;
		cnt++;
	}

	cout << cnt;
}

 

  정답  코드  

#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';
}

 

  리뷰  

정답 코드가 내 코드보다 효율적으로 동작함

이 문제에서는 입력으로 들어오는 수가 작아서 내 코드도 괜찮았는데

입력이 커지면 시간 초과 뜰 듯