* Computer Science/Algorithm

baekjun 1463. 1로 만들기

soicem 2018. 8. 2. 23:38

 기본 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, -1sizeof(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