[백준] 9095 - 1,2,3 더하기

1. 문제

9095번: 1, 2, 3 더하기

2. 개요

정수 n이 주어졌을 때 이 수를 1,2,3 만의 합으로 나타내는 경우의 수를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

먼저 dp 테이블을 작성한다.

dp[4]부터는 다시 1,2,3 만의 합으로 이루어진 수 + 1,2,3으로 나타낼 수 있으므로

dp[n] = dp[n-3] + dp[n-2] + dp[n-1]이 성립한다.

이를 이용해 dp테이블을 먼저 완성한 뒤 입력받은 수에 따라 해당 dp테이블에서 값을 출력한다.

3-2. Python

import sys

dp = [0 for _ in range(12)]
dp[1] = 1
dp[2] = 2
dp[3] = 4

for i in range(4, 12):
    dp[i] = dp[i-3] + dp[i-2] + dp[i-1]

T = int(sys.stdin.readline())

for t in range(T):
    n = int(sys.stdin.readline())

    print(dp[n])

3-3. C#

namespace boj_9095
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int[] dp = new int[12];

            dp[1] = 1;
            dp[2] = 2;
            dp[3] = 4;

            for (int i = 4; i < 12; i++)
                dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];

            int T = int.Parse(Console.ReadLine());

            for (int t = 0; t < T; t++)
            {
                int n = int.Parse(Console.ReadLine());
                Console.WriteLine(dp[n]);
            }
        }
    }
}