1로 만들기

문제 링크

앞으로 배우게 될 그래프 탐색과 최단 경로 문제의 1차원 버전이다.

발상

어떤 숫자 $i$를 만들 수 있는 이전 수는 $i+1,2i,3i$ 3가지 밖에 없다. 따라서 그 이전 수들 중 가장 작은 횟수로 만들어진 수를 구하고 그 수를 만드는데 필요한 연산 횟수에 1회의 추가 연산을 하면 현재 수를 만드는데 필요한 최소 연산 횟수를 구할 수 있다. 인자는 수 그 자체가 인자이며 기저 사례는 수가 $n$일 때 필요한 연산 0회다.

점화식

$$\{\begin{array}{l}{n}_i=\text{i를 만드는데 필요한 최소 연산 횟수}\end{array}$$ $$n_i=\min (n_{i+1},n_{2i},n_{3i})+1$$

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
	int n; cin >> n; vector<int> dp(n + 1, 21e8);
	dp[n] = 0; // 첫 수는 0회 연산
	for(int i=n-1; i>=1;i--) {
		int s1 = dp[i + 1];
		int s2 = i * 2 <= n ? dp[i * 2] : 21e8;
		int s3 = i * 3 <= n ? dp[i * 3] : 21e8;
		dp[i] = min({s1, s2, s3}) + 1; // 3개 중 가장 적은 횟수
	}
	cout << dp[1];
	return 0;
}