2022.02.06 [백준] C# 파도반 수열

 

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

9461번: 파도반 수열

 

---

풀이

이 문제는 먼저 수열의 규칙을 찾아야 합니다. 우선 7번째의 삼각형인 4를 보면 2번째의 1과 6번째의 3의 변이 합쳐서 만들어진것을 확인할 수 있습니다. 또한 9번째의 7을 보면 8번째의 5와 4번째의 2가 합쳐져서 7이 되었죠!

그래서 저는 f(n) = f(n-1) + f(n-5)라는 식을 세웠고 이 식을 bottom-up방식을 사용하여 코드를 작성하였습니다.

처음 배열과 리턴형을 int로 해서 계속 틀렸다고 뜨더군요...반례를 못 찾던 중, 100을 넣으니 음수가 나와서 long형식으로 바꿨습니다...ㅜ.ㅜ

 

구글링 중, f(n) = f(n-2) + f(n-3)이라는 식도 있군요!!

using System;
using System.Text;
using System.IO;
 
class Program
{
    static long[] num;
    static long func(int n)
    {
        num[0] = 1;
        num[1] = 1;
        num[2] = 1;
        num[3] = 2;
        num[4] = 2;
        if (n > 4)
        {
            for (int i = 5; i < n; i++)
            {
                num[i] = num[i - 1] + num[i - 5];
            }
        }
        
        return num[n-1];
    }
    static void Main()
    {
        StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
        StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));
        StringBuilder sb = new StringBuilder();
        int n = int.Parse(sr.ReadLine());
        num = new long[101];
        for(int i = 0; i < n; i++)
        {
            int a = int.Parse(sr.ReadLine());
            sb.Append(func(a)+"\n");
        }
        sw.WriteLine(sb.ToString());
        sr.Close();
        sw.Close(); 
    } 
}