[이것이 코딩테스트다]1이 될 때까지(C++)

https://www.aladin.co.kr/shop/wproduct.aspx?ItemId=247882118

이것이 취업을 위한 코딩 테스트다 with 파이썬

해당 도서의 그리디 알고리즘 - 실전문제4 1이 될 때까지를 풀이한다.

 

<문제 조건>

어떤 수 N을 입력 받은 뒤, 아래의 두 가지 연산 중 하나를 반복적으로 선택하여 1을 만드는 최소의 횟수를 구하라.

1) N에서 1을 뺀다

2) N을 K로 나눈다. (단, N은 K의 배수)

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
using namespace std;

int N, K;

int main() {
	scanf("%d %d", &N, &K);
	int answer = 0;
	int tmp = N;

	while (tmp != 1) {
		if (tmp % K == 0) tmp /= K;
		else tmp -= 1;

		answer += 1;
	}

	printf("%d", answer);
}

<솔루션 도출>

1) 나누기는 빼기보다 N을 1에 더 빠르게 가깝게 해준다.

2) 따라서 N이 K로 나뉘어지면 무조건 K로 나누도록 하고, 그 이외의 경우에만 1을 빼도록 한다.