백준 C# - 9095 +)풀이

DP를 이용해서 풀어야한다.

DP알아보러 가기

C# - 다이나믹 프로그래밍(DP)

---

풀이

01 점화식 찾기

n= 1,2,3,4일때를 직접 그리면 서로의 관계를 찾아 볼 수 있다.

아래 그림을 보면 n = 4에서 n = 1,2,3의 조합으로 만들어지는 것을 확인할 수 있다.

점화식

---

코드 전문

using System;
namespace baek2
{
    class Program
    {
        static void Main()
        {
            int num = int.Parse(Console.ReadLine());
            
            while(num>0)
            {
                int n = int.Parse(Console.ReadLine());
                int[] dp = new int[n + 10];
                dp[0] = 1;
                dp[1] = 2;
                dp[2] = 4;
                for(int i = 3; i<n;i++)
                {
                    dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
                }
                Console.WriteLine(dp[n-1]);
                num--;
            }
        }
    }
}