코테/Greedy
[C/C++] 나동빈 1이 될 때까지, Greedy
상똥
2023. 2. 2. 14:52
문제
어떤 수 N이 1이 될 때까지 다음의 두 과정을 반복적으로 선택하여 수행하려 한다. 1. N-1 2. N÷K (단, N이 K로 나누어 떨어질 때) 예를 들어, N이 17일 경우 1번, 2번, 2번 차례로 수행하면 N은 1이 되며, 총 연산횟수는 3이다. N과 K가 주어질 때 연산 횟수를 최소화하여 N을 1로 만드는 프로그램을 작성하라. 첫째 줄에 N(1≤N≤100,000)과 K(1≤K≤100,000)가 주어지며 N은 항상 K보다 크거나 같다. |
코드
#include <stdio.h>
#include <iostream>
using namespace std;
int main() {
int N, K, num = 0;
cin >> N >> K;
if (K == 1) {
cout << N;
return 0;
}
while (1) {
if (N == 1)
break;
if (N < K) {
num += N - 1;
break;
}
if (N % K == 0) {
N = N / K;
num++;
}
else {
num += N % K;
N -= N % K; //N<K일 경우?????
}
}
cout << num;
}
풀이
1. N을 최대한 빨리 1로 만드는 것이 중요하므로, 먼저 N이 K로 나누어 떨어진다면 K로 나누고 그렇지 않다면 면 N을 N%K만큼 감소시키는 순서로 while문 프로그램을 작성한다.
(*K==1인 경우 연산이 종료되지 않으므로, K==1을 degenerate case로 여겨 N이 출력된 후 종료한다.)
(*연산 도중 N이 K보다 작아지는 경우를 고려한다.)
2. 연산을 하나 수행할 때 마다 num을 1씩 증가시킨다.
3. N이 1이 되면 break