210124|白駿1463|C++


1463号:1

🎈 問題を解く


まず、必要な演算回数を格納するARRを数値ごとに作成します.インデックス1から順に上昇し、各ケースで最小回数を判断しarrに保存する.絵を描くと分かりやすくなります!

逆に,それぞれの場合を考慮してアルゴリズムヘッダのmin関数を用いて判断する.
#include <iostream>
#include <algorithm>
using namespace std;

int arr[1000000];

int main() {
	int N;
	cin >> N;

	arr[1] = 0;
	
	for (int i = 2; i <= N; i++) {
		arr[i] = arr[i - 1] + 1;
		if (i % 3 == 0)
			arr[i] = min(arr[i / 3] + 1, arr[i]);
		if (i % 2 == 0)
			arr[i] = min(arr[i / 2] + 1, arr[i]);

	}
	cout << arr[N];
}