백준 9461

이건 대놓고 수열이라 오히려 점화식이 금방 보였다.

DP 치고 쉬워서 이거 푼다음 자신감 붙어서 여러개 도전했다가 싹 머리 깨졌다.

DP 어렵다. 많이 해봐야 할 듯.

 

https://www.acmicpc.net/problem/9461

9461번: 파도반 수열

using System;

namespace Padoban

{

    class b9461

    {

        static void solution(int N)

        {

            ulong[] P = new ulong[N];

            if(N < 3)

            {

                Console.WriteLine("1");

                return;

            }

            P[0] = 1; P[1] = 1; P[2] = 1;

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

            {

                P[i] = P[i-2] + P[i-3];

            }

            Console.WriteLine(P[N-1]);

        }

        static void Main(string[] args)

        {

            int T = int.Parse(Console.ReadLine());

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

            {

                int N = int.Parse(Console.ReadLine());

                solution(N);

            }

        }

    }

}