[백준 - C#] 9095번 베스트셀러

문제링크

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

9095번: 1, 2, 3 더하기

 

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다.
합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

조건

시간제한 : 2초
메모리 제한 : 128 MB

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.
각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다.
n은 양수이며 11보다 작다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

 

문제정리

1. 정수 n이 주어졌을 때 n을 1, 2, 3만 이용하여 합으로 나타내는 모든 방법의 수를 구해야합니다.
2. 1 <= n <= 11

이번 문제의 경우 침착하게 모든 경우의 수를 보다보면 하나의 규칙을 찾을 수 있습니다.

n과 방법의 수의 갯수를 보다보면 n=4의 경우 n 1,2,3을 모두 더 한 값이며 n=5의 경우 n 2,3,4의 result를 더한 값입니다.

n => result
1 => 1
2 => 2
3 => 4
4 => 7
5 => 13
6 => 24

그리하여 찾을 수 있는 점화식은 dp[n] = dp[n-3] + dp[n-2] + dp[n-1] 입니다.

 

C# 코드

static void Main(string[] args)
{
    StreamWriter writer = new StreamWriter(Console.OpenStandardOutput());
    StreamReader reader = new StreamReader(Console.OpenStandardInput());
 
    int t = int.Parse(reader.ReadLine());
    int[] dp = new int[12];
 
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;
 
    for (int i = 0; i < t; i++)
    {
        int n = int.Parse(reader.ReadLine());
 
        for (int j = 4; j <= n + 1; j++)
        {
            dp[j] = dp[j - 3] + dp[j - 2] + dp[j - 1];
        }
 
        writer.WriteLine(dp[n]);
    }
 
    writer.Close();
    reader.Close();
}

읽어주셔서 감사합니다 오늘도 즐거운 하루 되세요.