(1) [C++] 백준 No.1463 : 1로 만들기

문제

풀이

- 자세한 설명 : https://ldgeao99.tistory.com/entry/챕터3-2-다이나믹-프로그래밍2

<나의 풀이>

# C++(Top-down방식)

#include <iostream>

using namespace std;

int d[1000000] = {0};   // 1에서 1로 가는건 연산을 필요로 하지 않으므로 d[1] = 0, 그냥 모두 d[0~99] = 0

// N을 1로 만드는데 필요한 최소 연산횟수를 반환하는 함수
int getSmallestCalCount(int n)
{
    if (n <= 1)
        return d[n];
    
    else if (d[n] > 0)  // n >= 2 경우, d[n] > 0 이면 이미 계산된 결과가 있음을 의미하므로 바로 결과반환
        return d[n];
    
    else
    {
        // 모든 수에서 가능한 연산인 -1을 먼저 해준다.
        d[n] = getSmallestCalCount(n-1) + 1;

        // 2으로 나눌 수 있어서 2으로 나눈 경우, 위에서 계산한 연산횟수보다 작은 연산횟수를 가지는지 확인
        if( n%2 == 0)
        {
            int temp;
            temp = getSmallestCalCount(n/2) + 1;
            if (d[n] > temp)
                d[n] = temp;
        }
            
        // 3으로 나눌 수 있어서 3으로 나눈 경우, 위에서 계산한 연산횟수보다 작은 연산횟수를 가지는지 확인
        if( n%3 == 0)
        {
            int temp;
            temp = getSmallestCalCount(n/3) + 1;
            if (d[n] > temp) 
                d[n] = temp;
        }
            
        // 이 위치에 도달하는 순간 d 1개의 값이 정해짐.
        return d[n];   
    }
}

int main()
{
    int n;
    cin >> n;
    cout << getSmallestCalCount(n);
}

# C++(Bottom-up방식)

#include <iostream>

using namespace std;

int d[1000000] = {0};   // 1에서 1로 가는건 연산을 필요로 하지 않으므로 d[1] = 0, 그냥 모두 d[0~99] = 0

// N을 1로 만드는데 필요한 최소 연산횟수를 반환하는 함수
int getSmallestCalCount(int n)
{
    if (n <= 1)
        return d[n];
    
    else if (d[n] > 0)  // n >= 2 경우, d[n] > 0 이면 이미 계산된 결과가 있음을 의미하므로 바로 결과반환
        return d[n];
    
    else
    {
        for (int i = 2; i <= n; i++)
        {
            // 모든 수에서 가능한 연산인 -1을 먼저 해준다.
            d[i] = d[i-1] + 1;

            // 2으로 나눌 수 있어서 2으로 나눈 경우, 위에서 계산한 연산횟수보다 작은 연산횟수를 가지는지 확인
            if (i%2 == 0)
            {
                int temp;
                temp = d[i/2] + 1;
                if (d[i] > temp)
                    d[i] = temp;
            }
            
            // 3으로 나눌 수 있어서 3으로 나눈 경우, 위에서 계산한 연산횟수보다 작은 연산횟수를 가지는지 확인
            if (i%3 == 0)
            {
                int temp;
                temp = d[i/3] + 1;
                if (d[i] > temp)
                    d[i] = temp;
            }

            // 이 위치에 도달하는 순간 d 1개의 값이 정해짐.
        }
        return d[n];
    }
}

int main()
{
    int n;
    cin >> n;
    cout << getSmallestCalCount(n);
}

<백준 풀이>

# C(Top-down방식)

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

# C(Bottom-up방식)

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

# Java(Top-down방식)

import java.util.*;

public class Main {
    public static int[] d;
    public static int go(int n) {
        if (n == 1) {
            return 0;
        }
        if (d[n] > 0) {
            return d[n];
        }
        d[n] = go(n-1) + 1;
        if (n%2 == 0) {
            int temp = go(n/2)+1;
            if (d[n] > temp) {
                d[n] = temp;
            }
        }
        if (n%3 == 0) {
            int temp = go(n/3)+1;
            if (d[n] > temp) {
                d[n] = temp;
            }
        }
        return d[n];
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        d = new int[n+1];
        System.out.println(go(n));
    }
}

# Java(Bottom-up방식)

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] d = new int[n+1];
        d[1] = 0;
        for (int i=2; i<=n; i++) {
            d[i] = d[i-1] + 1;
            if (i%2 == 0 && d[i] > d[i/2] + 1) {
                d[i] = d[i/2] + 1;
            }
            if (i%3 == 0 && d[i] > d[i/3] + 1) {
                d[i] = d[i/3] + 1;
            }
        }
        System.out.println(d[n]);
    }
}