다이나믹 프로그래밍 한접시
[백준] 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 까지 선언해둔뒤, 모든 값을 계산해두고 필요한 요소만 골라 출력하는 방식을 사용했었다.
근데 그 방식이 살짝 마음에 들지 않아서 위에있는대로 리스트를 사용해서 필요한 구간까지만 연산을 진행하고 더 추가해야 하면 추가로 연산을 진행하는 방식으로 코드를 개선해 보았다.
