오늘 푼 문제

https://www.acmicpc.net/problem/1463

1로 만들기

• 풀이 방식
  n을 2부터 올라가면서 경우의 수를 생각했다. ( 0을 1로 만들기X, 1을 1로 만들기 1)
  반복문을 통해서 1을 빼는 경우의 수를 계산하고, 이 계산 결과와 3을 나누는 것과 2를 나누는 것을 비교한 후 최소값을 구하게되면 최소의 경우의 수가 나온다.

나의 풀이

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

int dp[1000000] = { 0, };

int main() {


	int n;
	cin >> n;
	for (int i = 2; i <= n; i++) {
		dp[i] = dp[i - 1] + 1;
		if (i % 3 == 0) {
			dp[i] = min(dp[i], dp[i / 3] + 1);
		}
		if (i % 2 == 0) {
			dp[i] = min(dp[i], dp[i / 2] + 1);
		}
	}

	cout << dp[n] << endl;

	return 0;
}