1로 만들기
문제의 원본은 여기서 확인하세요.
- 다이나믹 프로그래밍
dp[n] : n을 1로 만드는데 필요한 최소 연산 횟수
- 3으로 나누어 떨어지는 경우
dp[i] = dp[i / 3] + 1
- 2로 나누어 떨어지는 경우
dp[i] = dp[i / 2] + 1
- 1을 뺴는 경우
dp[i] = dp[i - 1] + 1;
위의 경우들의 최솟값으로 dp[i]를 채운다. 이 과정 이후에 dp[n]이 해가 된다.
#include <iostream>
#include <vector>
using namespace std;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
vector<int> dp(n + 3);
dp[0] = 0;
dp[1] = 0;
dp[2] = 1;
dp[3] = 1;
for (int i = 4; 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;
}