1이 될 때까지
문제 : N과 K가 주어질 때 N이 1이 될 때까지 1번 또는 2번 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오.
어떤 수 N이 1이 될 때까지 두 과정 중 하나를 선택하여 반복 수행해야 한다.
- N에서 1을 뺀다
- N을 K로 나눈다.
2번의 경우 N이 K로 나누어 질 때만 선택할 수 있다.
예시 ) N이 17, K가 4 일 때 1번의 과정을 한 번 수행하면 16이 되므로 이후 2번 과정을 2회 수행하면 N이 1이되도록 만들 수 있다. 이 경우 전체 과정을 실행한 횟수는 3회가 된다.
동빈나님 유튜브 영상에 나오는 문제를 보고 직접 풀어본 코드는 다음과 같다.
#include <bits/stdc++.h>
using namespace std;
int n, k;
int main(){
std::ios::sync_with_stdio(0);
std::cin.tie(0);
cin >> n >> k;
int count = 0;
while(n != 1){
if(k != 1 && n % k == 0){
n = n / k;
count++;
}else {
n -= 1;
count++;
}
}
cout << count << "\n";
return 0;
}먼저 n이 1이 될 때까지 반복해야 하므로 while문을 사용하였다. k가 1인 경우 무한 루프를 돌 수 있으므로 첫번째 조건문에 k가 1인 경우에는 해당하지 않도록 and 연산자를 사용해주었다.
k가 1인 경우를 처음에 간과해서 스스로 테스트 케이스를 만들어서 테스트 했을 때 답이 출력되지 않는 것을 보고 추가해보았다.
앞에 문제 푸는 건줄 알고 ㅋㅋㅋ 풀었는데 다 풀고 영상 돌려보니 찐 문제가 나왔다. 여기서는 애초에 조건에 K가 2보다 크거나 같다고 나온다..! 이러면 K가 1일 때 예외처리를 하지 않아도 된다.
문제
입력조건
첫째 줄에 N( 1 <= N <= 100,000 ) 과 K(2 <= K <= 100,000)가 공백을 기준으로 하여 각각 자연수로 주어진다.
출력 조건
첫째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최솟값을 출력한다.
그리디 알고리즘
횟수의 최솟값 을 출력하는 문제이므로 가능한 많이 나누는 것이 이 문제의 해결 방안이라고 한다.
즉, 나누어 떨어지 않을 때 1을 빼고 나누어 떨어질 때 k로 나누면 최소한의 연산으로 N을 1로 만들 수 있다.
다 풀어본 후에 동빈님이 짠 코드도 확인해 보았는데 해석하기가 어렵다..또르륵.. (이해가 안된다..!!)
참고 자료
이코테 그리디 & 구현
