[백준] 9461번: 파도반 수열 [C#]

예제 2) 1 100

나선형으로 증가하는 파도반 수영이 있다.

입력받은 값의 차례에 해당하는 파도반 수열의 값을 출력해주는 문제이다.

 

 

using System.IO;
using System.Text;
using System.Linq;
using System.Reflection.PortableExecutable;
using System.Security.Cryptography;
 
namespace 연습장
{
    internal class Program
    {
        static long[] dp = new long[101];
        static long last = 5;
        static StringBuilder sb = new StringBuilder();
        static void Main(string[] args)
        {
            long n = long.Parse(Console.ReadLine());
 
            dp[0] = 0;
            dp[1] = 1;
            dp[2] = 1;
            dp[3] = 1;
            dp[4] = 2;
 
            for (int i = 0; i < n; i++)
            {
                long P = long.Parse(Console.ReadLine());
 
                if (P <= 4)
                {
                    Console.WriteLine(dp[P]);
                    continue;
                }
 
                for (long k = last; k <= P; k++)
                {
                    dp[k] = dp[k - 5] + dp[k - 1];
                    last = k;
                }
 
 
                Console.WriteLine(dp[P]);
        }
    }
}
 

 

이 파도반 수열은 P[k] = P[k - 1] + P[k-5] 로 증가하는 규칙이 있다.
미리 주어진 1부터 10까지의 값을 미리 dp에 할당을 해두고 사용해야 하지만, 코드가 너무 쓸데없이 길어져서 최소한의 조건인 5까지만 미리 저장을 해 두었다.

그 후 P의 값 까지 계산을 해두고, 해당 지점을 저장 해 둔 뒤, 다시 계산을 해야 할 때 꺼내와서 시작점으로 삼아주었다.

 

그리고 파도반 수열의 증가폭은 아주 크기 때문에, int형으로 저장하면 오버플로우 문제가 발생 할 것이다.

반드시 long형으로 저장해두어야 한다.