다이나믹 프로그래밍 한접시

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

NaZZU 2024. 5. 3. 23:41

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
using System.IO;
using System.Text;
using System.Linq;
using System.Reflection.PortableExecutable;
using System.Security.Cryptography;
 
namespace 연습장
{
    internal class Program
    {
        static StringBuilder sb = new StringBuilder();
        static void Main(string[] args)
        {
            using var reader = new StreamReader(Console.OpenStandardInput());
            using var print = new StreamWriter(Console.OpenStandardOutput());
 
            _15988_boj boj = new _15988_boj();
 
            boj.boj_15988();
 
        }
    }
    internal class _15988_boj
    {
        public void boj_15988()
        {
            int t = int.Parse(Console.ReadLine());
 
            List<long> dp = new List<long>();
            dp.Add(1);
            dp.Add(1);
            dp.Add(2);
            dp.Add(4);
 
            for (int i = 0; i < t; i++)
            {
                int n = int.Parse(Console.ReadLine());
 
                for (int j = dp.Count; j <= n; j++)
                {
                    dp.Add((dp[j - 1+ dp[j - 2+ dp[j - 3]) % 1_000_000_009);
                }
                Console.WriteLine(dp[n]);
            }
 
        }
    }
}
 
cs

 

생각보다 너무 단순한 문제였어서 놀랐다.

그리고 처음에 짠 알고리즘은 dp 배열을 만든 뒤 재사용하지 않고 버리는 구조라서 시간초과가 났었다.

이후 짠 코드는 dp 배열을 가장 큰 테스트 케이스인 1_000_001 까지 선언해둔뒤, 모든 값을 계산해두고 필요한 요소만 골라 출력하는 방식을 사용했었다.

근데 그 방식이 살짝 마음에 들지 않아서 위에있는대로 리스트를 사용해서 필요한 구간까지만 연산을 진행하고 더 추가해야 하면 추가로 연산을 진행하는 방식으로 코드를 개선해 보았다.