백준) 1463 1로 만들기

1로 만들기

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

디피로 완전탐색하자.

덜 논리적이라 디피는 재귀로 풀곤하는데(2)(완전 거의 대부분) 포문풀이(1)와 속도 차이가 4배정도 난다.

또한 재귀적으로 나누기 3의 상태를 보는게(3) 더 빠르다. 아마 더 빨리 1에 가까워져서가 아닐까 싶다

(1)

#include <stdio.h>
 
int dp[1000001];
 
int main() {
    int n, i;
    scanf("%d", &n);
    dp[1] = 0, dp[2] = 1, dp[3] = 1;
    for (i = 4; i <= n; i++) {
        dp[i] = dp[i - 1] + 1;
        if (i % 2 == 0 && dp[i / 2] + 1 < dp[i])
            dp[i] = dp[i / 2] + 1;
        if (i % 3 == 0 && dp[i / 3] + 1 < dp[i])
            dp[i] = dp[i / 3] + 1;
    }
    printf("%d", dp[n]);
}

(2)

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
 
 
#define fail 987654321
 
 
int n, dp[1000001];
 
int func(int x) {
    if (x < 1)
        return fail;
 
    if (x == 1)
        return 0;
 
    int& ref = dp[x];
    if (ref != -1)
        return ref;
 
    int a = fail, b = fail, c = fail;
    if (x % 3 == 0)
        a = func(x / 3) + 1;
    if (x % 2 == 0)
        b = func(x / 2) + 1;
    c = func(x - 1) + 1;
    
    return ref = min(min(a, b), c);
}
 
int main() {
    scanf("%d", &n);
    memset(dp, -1, sizeof(dp));
    printf("%d", func(n));
 
    return 0;
}

(3)

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
 
 
#define fail 987654321
 
 
int n, dp[1000001];
 
int func(int x) {
    if (x < 1)
        return fail;
 
    if (x == 1)
        return 0;
 
    int& ref = dp[x];
    if (ref != -1)
        return ref;
 
    int a = fail, b = fail, c = fail;
    c = func(x - 1) + 1;
    if (x % 2 == 0)
        b = func(x / 2) + 1;
    if (x % 3 == 0)
        a = func(x / 3) + 1;
    
    return ref = min(min(a, b), c);
}
 
int main() {
    scanf("%d", &n);
    memset(dp, -1, sizeof(dp));
    printf("%d", func(n));
 
    return 0;
}