기본 dp 문제
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | #include <iostream> #include <cstring> #include <algorithm> #define MAX 0x12345678 int cache[1000001]; using namespace std; int makeOne(int N) { if (N == 1) return 0; int & ret = cache[N]; if (ret != -1) return ret; ret = MAX; if (N % 3 == 0) ret = min(ret, makeOne(N / 3) + 1); if (N % 2 == 0) ret = min(ret, makeOne(N / 2) + 1); return ret = min(ret, makeOne(N - 1) + 1); } int main() { int N; cin >> N; memset(cache, -1, sizeof(cache)); cout << makeOne(N) << endl; //system("pause"); return 0; } | cs |
'* Computer Science > Algorithm' 카테고리의 다른 글
baekjun 10844. 쉬운 계단 수 (0) | 2018.08.06 |
---|---|
baekjun 1005. ACM Craft (0) | 2018.08.06 |
baekjun 2579. 계단 오르기 (0) | 2018.08.02 |
baekjun 1923. 정수 삼각형 (0) | 2018.08.01 |
baekjun 1149. RGB거리 (0) | 2018.08.01 |