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

문제 링크입니다: https://www.acmicpc.net/problem/9095

규칙을 찾기 위해 직접 나열한 결과 간단한 점화식을 얻을 수 있었습니다.

/*

정수 4를 1, 2, 3의 조합으로 나타내는 방법은 총 7가지가 있다.

1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1

정수 n이 주어졌을 때, n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

*/

#include <iostream>

using namespace std;

 

int N; //주어진 정수

int cache[11]; //N<11

 

//풀어보면 점화식은 f(x)=f(x-1)+f(x-2)+f(x-3)

int method(void)

{

        cache[1] = 1; //1

        cache[2] = 2; //1+1, 2

        cache[3] = 4; //1+1+1, 1+2, 2+1, 3

        for (int i = 4; i <= N; i++)

               cache[i] = cache[i - 1] + cache[i - 2] + cache[i - 3];

        return cache[N];

}

 

int main(void)

{

        int test_case;

        cin >> test_case;

 

        for (int i = 0; i < test_case; i++)

        {

               cin >> N;

               cout << method() << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~