[그리디] Ch03-4

03-4| 1이 될 때까지

소요시간: 약 3분

🌷 초기 코드:

#include <iostream>
using namespace std;

int main() {
	int n, k = 0;
	cin >> n >> k;
	int cnt = 0;
	while (n!=1) {
		if (n%k == 0) {
			n = n / k;
			cnt++;
		}
		else {
			n = n - 1;
			cnt++;
		}
	}
	cout << cnt;

	return 0;
}

🌼 개선할 점:

• 핵심 아이디어는 나누기를 최대한 많이 하기이다. 책에 나와있는 코드는(3-5.py) 보다 복잡하게 짜여있는데, 내 코드에서는 먼저 나누어 떨어지는지 확인 후 아닐 경우에만 빼기를 수행하므로 똑같이 동작할 것으로 생각된다.
• n의 범위가 커질 경우에는 n이 k의 배수가 되도록 한번에 빼는 방식을 사용하자.

🌻 수정된 코드:

#include <iostream>
using namespace std;

int main() {
	int n, k = 0;
	cin >> n >> k;
	int cnt = 0;
	int tmp = 0;
	while (true) {
		tmp = (n / k)*k; // n=19, k=4이면 tmp=4*4=16
		cnt += (n - tmp); // 나머지를 한번에 더함 (19-16=3)
		n = tmp;
		if (n < k) {
			break;
		}
		n = n / k;
		cnt++;
	}
	cnt += (n - 1); // 나머지 n이 1이 되기 전까지 뺌
	cout << cnt;

	return 0;
}

• BOJ 36
• Algorithm 12
• CodingTest 11
• Web 9
• Javascript 8
• Vue 7
• React 7
• DBProject 4
• Python 3
• Tech-interview 3
• Express 3
• Next 3
• Github 2
• Django 2
• C 1
• C++ 1
• WebGame 1