백준 9095번 1,2,3더하기

문제

코드

// 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을 하면 되니 이를 이용하여 다이나믹 프로그래밍으로 풀었다.

난이도

하

결과