[ BOJ/C# ] 9095 1, 2, 3 더하기

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

9095번: 1, 2, 3 더하기

이 문제도 다이나믹 프로그래밍 문제이다. 마찬가지로 초반에 어느 정도 직접 구해보며 규칙을 찾아야 한다. 

 

n==1일 경우 1로 1개의 방법, 

n==2일 경우 1+1, 2로 2개

n==3일 경우 1+1+1, 1+2, 2+1, 3으로 4개, 

n==4일 경우 문제의 예시를 참고하면 된다. 

 

처음에는 왜인지 단일 숫자만으로는 안된다고 생각했다..그때문인지 n==7까지 구해봤다

예시가 n==4일 경우로 나온것으로 보아, 아마 출제자의 함정이 아니었을까 싶다😂

 

이렇게 예시를 구해보면 1, 2, 4, 7, 13, 24, 44..가 나온다. 

규칙성을 찾아보면 n>=4이면

(n-1)의 방법의 수 + (n-2)의 방법의 수 + (n-3)의 방법의 수를 더한 값과 같다는 것을 알 수 있다. 

이를 다음과 같이 재귀함수로 작성할 수 있다. 

using System;
using System.Text;

namespace B9095
{
    class Program
    {
        static void Main()
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
            StringBuilder sb = new StringBuilder();

            int t = int.Parse(sr.ReadLine());
            for(int i = 0; i < t; i++)
            {
                int n = int.Parse(sr.ReadLine());
                sb.Append(GetCase(n) + "\n");
            }
            sw.Write(sb);
            sr.Close();
            sw.Flush();
            sw.Close();
        }

        static int GetCase(int n)   //방법의 수 구하기
        {
            if (n <= 2) return n;
            else if (n == 3) return 4;
            else return GetCase(n - 1) + GetCase(n - 2) + GetCase(n - 3);   //점화식
        }
    }
}