[백준] 1463번: 1로 만들기

1463번: 1로 만들기

 

1을 뺐을때 연산의 갯수, 2로 나눠질때의 연산의 갯수, 3으로 나눠질때의 연산의 갯수 중 최소값을 배열에 저장한다.

#include<iostream>
#include<algorithm>
#define MAX 1000001
using namespace std;

int main() {
	int n;
	int num[MAX];

	cin >> n;

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

	cout << num[n];
}