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

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

1463번: 1로 만들기

🔔 문제 : 

정수 X에 3가지 연산만 사용할 수 있습니다.

 

1. X가 3으로 나눠지면, 3으로 나눌 수 있습니다.

2. X가 2로 나눠지면, 2로 나눌 수 있습니다.

3. 1을 뺍니다.

 

정수 X이 주어졌을 때, 연산을 사용하는 횟수의 최솟값을 출력하는 문제입니다.

 

정수는 1보다 크거나 같고, 10^6 작거나 같은 정수 입니다.

---

🔔 Kick Point :

DP문제입니다.

O(n)의 시간 복잡도로 해결을 하며,  Bottom up 방식으로 풀 것이고 1씩 더하는 조건을 기본 디폴트로 둡니다.

 

즉 F(n) 일 때, min (F(n-1), F(n/2), F(n/3)) 을 찾는 것으로 나눌 수 있습니다.

 

---

🔔 Code :

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

// F(n) = Min(F(n/3), F(n/2), F(n-1))

int main() {
	int n; cin >> n;
	vector<int> dp(n+1);

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

	cout << dp[n];
}

---