[백준] C# 9095번 : 1, 2, 3 더하기

문제

 

5를 1,2,3으로 나타낸 경우의 수는 13이다.

4을 1,2,3으로 나타낸 경우의 수는 7이다.

3의 경우의 수는 4이다.

2의 경우의 수는 2이다.

1의 경우의 수는 1이다.

 

규칙이 아리까리해서 헷갈렸지만 알고 보니 쉬웠다!

4는

"1" + 3

"2" + 2

"3" + 1

으로 나타낼 수 있고,

1+ 로 시작하는 경우의 수는 3을 1,2,3으로 나타낸 경우의 수와 같다. 마찬가지로

2+로 시작하는 경우의 수는 2를 1,2,3으로 나타낸 경우의 수와 같다.

3+로 시작하는 경우의 수는 1을 1,2,3으로 나타낸 경우의 수와 같다.

따라서 위 경우의 수를 모두 더해주면 4를 1,2,3으로 나타낸 경우의 수(1+2+4)를 구할 수 있다.

 

5를 구할 경우에는 마찬가지로

1+4 (=> 1+로 시작하는 경우의 수는 4를 1,2,3으로 나타낸 경우의 수와 같다)

2+3 (=> 2+로 시작하는 경우의 수는 3을 1,2,3으로 나타낸 경우의 수와 같다)

3+2

이다.

 

즉, 이를 함수로 나타내면

dp[n] = dp[n-3] + dp[n-2] + dp[n-1]

가 된다.

 

나는 숫자 1, 2, 3의 경우의 수는 사람이 쉽게 구할 수 있으므로 간단하게 switch문과 재귀함수를 활용했다.

 

내가 푼 코드

 

using System;

namespace Practice
{
    class Program
    {
        static int Main(string[] args)
        {
            int count = int.Parse(Console.ReadLine());
            int[] numbers = new int[count];

            for (int i = 0; i < count; i++)
                numbers[i] = int.Parse(Console.ReadLine());

            for (int i = 0; i < count; i++)
                Console.WriteLine(Calculate(numbers[i]));

            return 0;
        }

        static int Calculate(int number)
        {
            int result = 0;

            switch (number)
            {
                case 1:
                    result = 1;
                    break;
                case 2:
                    result = 2;
                    break;
                case 3:
                    result = 4;
                    break;
            }

            if (number >= 4)
            {
                result = Calculate(number - 1) + Calculate(number - 2) + Calculate(number - 3);
            }

            return result;
        }
    }
}