(C++) [백준] 1로 만들기

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

1463번: 1로 만들기

 

 

요약 )

1. 1 이상 100,000 이하의 수를 입력한다
2. 문제 보기에 주어진 3개의 연산을 적절하게 사용해서 1로 만들어준다
3. 이 과정에서 사용한 연산의 최소 개수를 출력해 준다.

 

#include <iostream>
#include <algorithm>

using namespace std;

int make_one[1000001];

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

	for (int i = 2; i <= x; i++) {
		make_one[i] = make_one[i - 1] + 1;

		if (i % 2 == 0) {
			make_one[i] = min(make_one[i], make_one[i / 2] + 1);
		}
		if (i % 3 == 0) {
			make_one[i] = min(make_one[i], make_one[i / 3] + 1);
		}
	}
	cout << make_one[x] << endl;
	return 0;

}