#include <iostream> #include <algorithm> using namespace std; int num; int dp[1000010]; int solve(int n) { if(n == 1) { return 0; } if(dp[n] != 99999999) { return dp[n]; } if(n % 3 == 0) { dp[n] = min(dp[n], solve(n/3) + 1); } if(n % 2 == 0) { dp[n] = min(dp[n], solve(n/2) + 1); } if(n - 1 != 0) { dp[n] = min(dp[n], solve(n-1) + 1); } return dp[n]; } int main(void) { // freopen("B1463_input.txt", "r", stdin); cin >> num; for(int i = 0; i < 1000010; i++) { dp[i] = 99999999; } cout << solve(num); return 0; } | cs |
'Baekjoon > DP' 카테고리의 다른 글
[백준 11057] 오르막 수 (DP) (C/C++) (★) (0) | 2020.01.17 |
---|---|
[백준 10844] 쉬운 계단수 (DP) (C/C++) (0) | 2020.01.17 |
[백준 9095] 1, 2, 3 더하기 (DP) (C/C++) (0) | 2020.01.16 |
[백준 11727] 2xN 타일링2 (DP) (C/C++) (0) | 2020.01.16 |
[백준 11726] 2xN 타일링 (DP) (C/C++) (0) | 2020.01.16 |