나선형으로 증가하는 파도반 수영이 있다.
입력받은 값의 차례에 해당하는 파도반 수열의 값을 출력해주는 문제이다.
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
|
using System.IO;
using System.Text;
using System.Linq;
using System.Reflection.PortableExecutable;
using System.Security.Cryptography;
namespace 연습장
{
internal class Program
{
static long[] dp = new long[101];
static long last = 5;
static StringBuilder sb = new StringBuilder();
static void Main(string[] args)
{
long n = long.Parse(Console.ReadLine());
dp[0] = 0;
dp[1] = 1;
dp[2] = 1;
dp[3] = 1;
dp[4] = 2;
for (int i = 0; i < n; i++)
{
long P = long.Parse(Console.ReadLine());
if (P <= 4)
{
Console.WriteLine(dp[P]);
continue;
}
for (long k = last; k <= P; k++)
{
dp[k] = dp[k - 5] + dp[k - 1];
last = k;
}
Console.WriteLine(dp[P]);
}
}
}
|
cs |
이 파도반 수열은 P[k] = P[k - 1] + P[k-5] 로 증가하는 규칙이 있다.
미리 주어진 1부터 10까지의 값을 미리 dp에 할당을 해두고 사용해야 하지만, 코드가 너무 쓸데없이 길어져서 최소한의 조건인 5까지만 미리 저장을 해 두었다.
그 후 P의 값 까지 계산을 해두고, 해당 지점을 저장 해 둔 뒤, 다시 계산을 해야 할 때 꺼내와서 시작점으로 삼아주었다.
그리고 파도반 수열의 증가폭은 아주 크기 때문에, int형으로 저장하면 오버플로우 문제가 발생 할 것이다.
반드시 long형으로 저장해두어야 한다.
'다이나믹 프로그래밍 한접시' 카테고리의 다른 글
[백준] 1890번: 점프 [C#] (0) | 2024.04.10 |
---|---|
[백준] 2294번: 동전 2 [C#] (0) | 2024.04.09 |
[백준] 9465번: 스티커 [C#] (0) | 2024.04.09 |
[백준] 계단 오르기 [C#] (0) | 2024.04.08 |
[백준] 22115번: 창영이와 커피 [C#] (1) | 2024.04.08 |