다이나믹 프로그래밍 한접시
[백준] 9461번: 파도반 수열 [C#]
NaZZU
2024. 4. 9. 19:14

나선형으로 증가하는 파도반 수영이 있다.
입력받은 값의 차례에 해당하는 파도반 수열의 값을 출력해주는 문제이다.
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형으로 저장해두어야 한다.
