알고리즘/다이나믹프로그래밍

Dynamic알고리즘[1463번]

leo_____lee 2018. 11. 2. 16:05

소스

c++

함수만 이용
#include <iostream>
#define MIN(X,Y) (X < Y ? X:Y);
using namespace std;

//void dynamic1(int* arr, int size);
int main()
{
    int i = 4;
    int re3 = 0;
    int re2 = 0;
    int minVal = 0;
    long long val=0;
    cin >> val;
    while (val > 1000001 || val<0) {
        cin >> val;
    }
    int* arr = new int[val+1];
    arr[0] = 0;
    arr[1] = 0;
    arr[2] = 1;
    arr[3] = 1;
//    dynamic1(arr, val);
    if (val > 3) {
        while (!(i == val + 1)) {

            arr[i] = arr[i - 1] + 1;
            if (i % 3 == 0) {
                arr[i] = MIN(arr[i / 3] + 1, arr[i]);
            }
            if (i % 2 == 0) {
                arr[i] = MIN(arr[i / 2] + 1, arr[i]);
            }
            i++;
        }
    }
    cout << arr[val];
    if(val>2)delete[] arr;
    return 0;
}
클래스를 이용
#include <iostream>
#define Min(a,b) (a<b?a:b);
using namespace std;
class ex_1463{

private:
    int* m_nArr;
    int m_nVal;

public:
    ex_1463(int input) {
        m_nVal = input;
        m_nArr = new int[m_nVal+1];
    }
    ~ex_1463() {
        delete[] m_nArr;
    }

    void SetVal(int input) {
        m_nVal = input;
    }
    void SetArr(const int* arr) {

    }
    void GetVal() {

    }
    void GetArr() {

    }

    int makeArr() {

        m_nArr[0] = 0;
        m_nArr[1] = 0;
        m_nArr[2] = 1;
        m_nArr[3] = 1;
        for (int i = 4; i < m_nVal+1;i++) {
            m_nArr[i] = m_nArr[i - 1] + 1;
            if (i % 3 == 0) {
                m_nArr[i] = Min(m_nArr[i], m_nArr[i / 3] + 1);
            }
            if (i % 2 == 0) {
                m_nArr[i] = Min(m_nArr[i], m_nArr[i / 2] + 1);
            }
        }
        return m_nArr[m_nVal];
    }
};

int main() {

    long long val;
    cin >> val;
    while (val > 1000001 || val<0) {
        cin >> val;
    }
    ex_1463 ex(val);
    int x = ex.makeArr();
    cout << x;
    return 0;
}

실수했던 점

    int makeArr() {

        m_nArr[0] = 0;
        m_nArr[1] = 0;
        m_nArr[2] = 1;
        m_nArr[3] = 1;
        for (int i = 4; i < m_nVal+1;i++) {
            m_nArr[i] = m_nArr[i - 1] + 1;
            if (i % 3 == 0) {
                m_nArr[i] = Min(m_nArr[i], m_nArr[i / 3] + 1);
            }
            if (i % 2 == 0) {
                m_nArr[i] = Min(m_nArr[i], m_nArr[i / 2] + 1);
            }
        }
        return m_nArr[m_nVal];
    }
};

이부분에서 m_nArr[i] = Min(m_nArr[i], m_nArr[i / 3] + 1); 이부분을 m_nArr[i] = Min(m_nArr[i-1]+1, m_nArr[i / 3] + 1);로 계속 하는 실수를 했다....

결과