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

 

예전에 풀었던 1, 2, 5로 숫자 만들기 문제와 비슷하지만, 이번에는 숫자의 조합을 다르게 하면 다른 경우의 수로 인정을 해주는 문제이다.

이전에는 dp[i] += dp[i - n] ( i = dp의 현재 인덱스, n은 1, 2, 5 중 하나) 로 풀었지만, 이번에는 다른 접근이 필요할 것 같다.

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace 연습장
{
    internal class _9095_boj
    {
        public void boj_9095()
        {
            int N = int.Parse(Console.ReadLine());
 
            List<int> dp = new List<int>();
            dp.Add(0);
            dp.Add(1);
            dp.Add(2);
            dp.Add(4);
 
            for (int i = 0; i < N; i++)
            {
                int input = int.Parse(Console.ReadLine());
 
                if (input <= 3)
                {
                    Console.WriteLine(dp[input]);
                    continue;
                }
 
                for (int j = dp.Count; j <= input; j++)
                {
                    dp.Add(dp[j - 3] + dp[j - 2] + dp[j - 1]);
                }
 
                Console.WriteLine(dp[input]);
 
 
            }
        }
    }
}
 

 

열심히 규칙을 찾아보려고 그림을 그려 보던 중 3, 2, 1 칸 전의 값들의 합이 이번 칸의 값이라는걸 알아냈다.

이후 코드로 구현했더니 정답이었다.