1로 만들기

문제

정수 X가 주어졌을 때 사용할 수 있는 연산 4가지

• 5로 나누어떨어지면 5로 나눈다
• 3으로 나누어떨어지면 3으로 나눈다
• 2로 나누어떨어지면 2로 나누다
• 1을 뺀다

연산 4개를 사용하여 1을 만들기 위한 최소 연산 횟수

입력

정수 X (1<=X<=30,000)

출력

연산을 위한 최소 횟수

풀이

2부터 X까지 증가하면서 각각의 연산을 했을때의 회수의 최솟값을 배열에 저장
X-1의 최소 횟수보다 1만큼 크다는 전제하에 비교하기

#include<iostream>
#include<vector>
#include<algorithm>

#define MAXN 30001

using namespace std;

int cnt[MAXN] = { 0, };


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int N;
	cin >> N;

	for (int i = 2; i <= N; i++) {
		cnt[i] = cnt[i - 1] + 1;

		if (i % 2 == 0) {
			cnt[i] = min(cnt[i], cnt[i / 2] + 1);
		}
		if (i % 3 == 0) {
			cnt[i] = min(cnt[i], cnt[i / 3] + 1);
		}
		if (i % 5 == 0) {
			cnt[i] = min(cnt[i], cnt[i / 5] + 1);
		}
	}

	cout << cnt[N];



	return 0;
}