문제

풀이

#include <iostream>
using namespace std;

class bj11726 {
private:
    int m_nVal;
    int* m_pArr;

public:
    bj11726() {

    }
    bj11726(int& val) {
        while (val > 1 || val > 1000) {
            cin >> val;
        }
        m_nVal = val;
        m_pArr = new int[m_nVal];
    }
    ~bj11726() {
        delete[] m_pArr;
    }
    void SetVal() {
        cin >> m_nVal;
        while (m_nVal < 1 || m_nVal > 1000) {
            cin >> m_nVal;
        }
        m_pArr = new int[m_nVal];
    }
    void SetArr() {
        int i = 0;
        if (m_nVal == 1) m_pArr[0] = 1;
        else if (m_nVal == 2) {
            m_pArr[0] = 1;
            m_pArr[1] = 3;
        }
        else {
            m_pArr[0] = 1;
            m_pArr[1] = 3;
            m_pArr[2] = 5;

            i = 3;
            while (i < m_nVal) {
                m_pArr[i] = (m_pArr[i - 1] + 2 * m_pArr[i - 2]) % 10007;
                i++;
            }
        }
    }
    void printResult() {
        cout << m_pArr[m_nVal - 1];
    }
};

int main()
{
    bj11726 ex;
    ex.SetVal();
    ex.SetArr();
    ex.printResult();
    return 0;
}

풀이방법

끝에 부분이 다른 경우는 이전칸에서 2*1이 들어가는 경우. 전전칸에서 2*2나 1*2로 이루진 것이 들어가는 경우이다.m_pArr[i] = m_pArr[i - 1] + 2 * m_pArr[i - 2]

결과

문제

코드

// bj11726.cpp: 콘솔 응용 프로그램의 진입점을 정의합니다.
//
#include "stdafx.h"
#include <iostream>
using namespace std;

class BJ9095 {
private:
    int testNum;
    int *testArr;
    int *resultArr;
public:
    BJ9095() {

    }
    ~BJ9095() {
        delete[] testArr;
    }
    void SetArr() {
        cin >> testNum;
        while (testNum < 1 || testNum>10) {
            cin >> testNum;
        }
        testArr = new int[testNum];
        resultArr = new int[testNum];
        for (int i = 0; i < testNum; i++)
            cin>>testArr[i];
    }
    void PrintArr() {
        for (int i = 0; i < testNum; i++) {
            cout << resultArr[i]<<endl;
        }
    }
    void SetResult() {

        for (int i = 0; i < testNum; i++) {
            int* arr;
            arr = new int[testArr[i]];
            if (testArr[i] == 1) {
                arr[0] = 1;
            }
            else if (testArr[i] == 2) {
                arr[0] = 1;
                arr[1] = 2;
            }
            else if (testArr[i] == 3) {
                arr[0] = 1;
                arr[1] = 2;
                arr[2] = 4;
            }
            else {
                arr[0] = 1;
                arr[1] = 2;
                arr[2] = 4;
                for (int j = 3; j < testArr[i]; j++) {
                    arr[j] = arr[j - 1] + arr[j - 2] + arr[j - 3];
                }
            }
            resultArr[i] = arr[testArr[i] - 1];
            delete[] arr;
        }

    }

};

int main()
{
    BJ9095 test;
    test.SetArr();
    test.SetResult();
    test.PrintArr();

    return 0;
}

풀이방법

arr[j] = arr[j - 1] + arr[j - 2] + arr[j - 3]

풀이방법은 생각해보면 T[N]을 만들기 위해서는 그전항, 그전전항, 그전전전항에 각가 +1,+2,+3을 하면 되니 이를 이용하여 다이나믹 프로그래밍으로 풀었다.

난이도

하

결과

코드

풀이1

#include <iostream>
using namespace std;

class bj11726{
private:
    int m_nVal;
    int* m_pArr;

public:
    bj11726() {

    }
    bj11726(int& val) {
        while (val > 1 || val > 1000) {
            cin >> val;
        }
        m_nVal = val;
        m_pArr = new int[m_nVal];
    }
    ~bj11726() {
        delete[] m_pArr;
    }
    void SetVal() {
        cin >> m_nVal;
        while (m_nVal < 1 || m_nVal > 1000) {
            cin >> m_nVal;
        }
        m_pArr = new int[m_nVal];
    }
    void SetArr() {
        int i = 0;
        if (m_nVal == 1) m_pArr[0] = 1;
        else if (m_nVal == 2) {
            m_pArr[0] = 1;
            m_pArr[1] = 2;
        }
        else {
            m_pArr[0] = 1;
            m_pArr[1] = 2;
            m_pArr[2] = 3;

            i = 3;
            while (i < m_nVal) {
                m_pArr[i] = (m_pArr[i - 1]+m_pArr[i-2])%10007 ;
                i++;
            }
        }
    }
    void printResult() {
        cout << m_pArr[m_nVal-1];
    }
};

int main()
{
    bj11726 ex;
    ex.SetVal();
    ex.SetArr();
    ex.printResult();
    return 0;
}

그냥 넘어가기 아쉬워서...T[N]=T[N-1]+T[N-2]=T[N-2]+T[N-3]+T[N-2]=2T[N-2]+T[N-3]을 증명

// bj11726.cpp: 콘솔 응용 프로그램의 진입점을 정의합니다.
//
#include "stdafx.h"
#include <iostream>
using namespace std;

class bj11726{
private:
    int m_nVal;
    int* m_pArr;

public:
    bj11726() {

    }
    bj11726(int& val) {
        while (val > 1 || val > 1000) {
            cin >> val;
        }
        m_nVal = val;
        m_pArr = new int[m_nVal];
    }
    ~bj11726() {
        delete[] m_pArr;
    }
    void SetVal() {
        cin >> m_nVal;
        while (m_nVal < 1 || m_nVal > 1000) {
            cin >> m_nVal;
        }
        m_pArr = new int[m_nVal];
    }
    void SetArr() {
        int i = 0;
        if (m_nVal == 1) m_pArr[0] = 1;
        else if (m_nVal == 2) {
            m_pArr[0] = 1;
            m_pArr[1] = 2;
        }
        else {
            m_pArr[0] = 1;
            m_pArr[1] = 2;
            m_pArr[2] = 3;

            i = 3;
            while (i < m_nVal) {
                m_pArr[i] = (m_pArr[i - 3]+2*m_pArr[i-2])%10007 ;
                i++;
            }
        }
    }
    void printResult() {
        cout << m_pArr[m_nVal-1];
    }
};

int main()
{
    bj11726 ex;
    ex.SetVal();
    ex.SetArr();
    ex.printResult();
    return 0;
}

결과

실수한점

뒤에 런타임 에러로 인해 백준 사이트에서 100007로 나머지를 구하라 하였는데 귀찮아서 안했다가 두번이나 틀렸다...

소스

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);로 계속 하는 실수를 했다....

결과