(https://www.acmicpc.net/problem/9095)

1 : 1

2 : 1+1, 2

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

4 : 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 1+3, 3+1, 2+2, 4

갯수의 연관이 결국은 구성의 연관과 같은 것이다.

갯수의 연관관계가 보이지 않는다면, 구성적인 연관관계를 생각하자.

“5” 이상부터는 갯수가 기하급수적으로 많아져 세보기가 쉽지않다. “4”까지의 구성적 연관을 살펴보자.

4의 구성원들은 , (1의 구성원들 +3), (2의 구성원들 +2), (3의 구성원들 +1)의 구성인것을 알수 있다.

-> (“1”+3) (“1+1”+2, “2”+2) (“1+1+1”+1, “1+2”+1, “2+1”+1, “3”+1)

따라서 d[4] = d[3] + d[2] + d[1]이므로,

점화식은 d[n] = d[n-1] + d[n-2] + d[n-3].

bottom-top으로 쉽게 풀수 있는데, 난 굳이 top-bottom으로 품….ㅠ

C++ 코드(bottom-top)

#include <iostream>
using namespace std;

int main() {
	int d[12] = {};
	d[1] = 1, d[2] = 2, d[3] = 4;

	int t; cin >> t;
	while (t--) {
		int n; cin >> n;
		for (int i = 4; i <= n; i++)
			d[i] = d[i - 1] + d[i - 2] + d[i - 3];
		cout << d[n] << '\n';
	}

}

C++ 코드(top-bottom)

#include <iostream>

using namespace std;

int dp(int n, int& count) {
	if (n <= 0) {
		if (n == 0) count++;
		return n;
	}
	
	if (n >= 3) dp(n - 3, count);
	dp(n - 1, count);
	dp(n - 2, count);

	return 0;
}

int main() {
	int N = 0;
	scanf("%d", &N);

	while (N--) {
		int n = 0;
		int count = 0;
		scanf("%d", &n);
		dp(n, count);
		printf("%d\n", count);
	}
	return 0;
}

C# 코드

using System.Text;
using System;
using static System.Console;

class Program
{
    static int[] arr = new int[12];
    public static void Main(string[] args)
    {
        arr[1] = 1;
        arr[2] = 2;
        arr[3] = 4;
        int T = int.Parse(ReadLine());
        for(int i = 0; i< T; i++)
        {
            int n = int.Parse(ReadLine());
            if (arr[n] > 0) WriteLine(arr[n]);
            else
            {
                for(int j = 4; j<= n; j++)
                {
                    arr[j] = arr[j - 1] + arr[j - 2] + arr[j - 3];
                }
                WriteLine(arr[n]);
            }
        }


    }
}

Java 코드

import java.util.*;

public class Main {
    static int[] arr = new int[11];

    public static void main(String[] args) {
        arr[1] = 1; arr[2] = 2; arr[3] = 4;
        Scanner s = new Scanner(System.in);
        int T = s.nextInt();
        for(int i = 0; i<T; i++){
            int n = s.nextInt();
            if(arr[n] > 0) System.out.println(arr[n]);
            else{
                for(int j = 4; j <=n; j++){
                    arr[j] = arr[j-1] + arr[j-2] + arr[j-3];
                }
                System.out.println(arr[n]);
            }
        }

    }
}

Kotlin 코드

import java.util.*
import kotlin.math.*

fun main(args: Array<String>){
    val arr = IntArray(11)
    arr[1] = 1; arr[2] = 2; arr[3] = 4;
    val s = Scanner(System.`in`)
    val T = s.nextInt()
    for(i in 1..T){
        val n = s.nextInt()
        if(arr[n] > 0) println("${arr[n]}")
        else{
            for(j in 4..n){
                arr[j] = arr[j-1] + arr[j-2] + arr[j-3];
            }
            println(arr[n])
        }
    }
}

Python 코드

arr = [0 for _ in range(11)]
arr[1] = 1; arr[2] = 2;  arr[3] = 4
T = int(input())
for i in range(T):
    n = int(input())
    if arr[n] > 0: print(arr[n])
    else:
        for j in range(4, n+1):
            arr[j] = arr[j-1] +arr[j-2] +arr[j-3]
        print(arr[n])