[C/C++] 나동빈 1이 될 때까지, Greedy

문제

어떤 수 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