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

1. 문제

15988번: 1, 2, 3 더하기 3

2. 개요

정수 n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

n ≥ 4 일때, dp[n] = dp[n - 1] + dp[n - 2] + dp[n - 3]이다.

이를 이용해 답을 구한다.

3-2. Python

import sys

dp = [0 for i in range(1000001)]

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

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

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

for i in range(N):
    print(dp[int(sys.stdin.readline())])

3-3. C#

namespace boj_15988
{
    internal class Program
    {
        static void Main(string[] args)
        {
            long[] dp = new long[1000001];

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

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

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

            for (int i = 0; i < N; i++)
                Console.WriteLine(dp[int.Parse(Console.ReadLine())]);
        }
    }
}