다이나믹 프로그래밍 한접시
[백준] 11727번: 2*n 타일링 2 [C#]
NaZZU
2024. 4. 28. 23:35
|
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
50
51
52
53
54
55
56
57
58
59
|
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());
_11727_boj boj = new _11727_boj();
boj.boj_11727();
}
}
internal class _11727_boj
{
public void boj_11727()
{
int n = int.Parse(Console.ReadLine());
int[] o_dp = new int[n + 2];
o_dp[0] = 0;
o_dp[1] = 1;
o_dp[2] = 2;
int[] n_dp = new int[n + 2];
n_dp[0] = 0;
n_dp[1] = 0;
n_dp[2] = 1;
int[] r_dp = new int[n + 2];
r_dp[0] = 0;
r_dp[1] = 1;
r_dp[2] = 3;
if (n <= 2)
{
Console.WriteLine(r_dp[n]);
return;
}
for (int i = 3; i <= n; i++)
{
o_dp[i] = (o_dp[i - 1] + o_dp[i - 2]) % 10007;
n_dp[i] = (r_dp[i - 2] + n_dp[i - 1] + n_dp[i - 2]) % 10007;
r_dp[i] = (n_dp[i] + o_dp[i]) % 10007;
}
Console.WriteLine(r_dp[n]);
}
}
}
|
cs |
저번 문제에서 풀었던 2*1 1*2 타일로만 이루어진 경우의 수를 담은 배열,
2 * 2 타일로도 이루어진 경우의 수를 담는 배열을 만들어서 연산을 해 주었다.
2 * 2 타일을 사용하는 경우는 2*2 타일을 할당 한 후 남은만큼의 공간의 새로운 배열의 값( r_dp[ i - 2 ] )을 넣어주고
2 * 1 타일을 사용하는 경우는 남은 공간의 원래 배열의 값 ( o_dp[ i - 1 ] )
1 * 2 타일을 사용하는 경우는 ( o_dp[ i - 2 ] ) 의 값을 사용해서 모두 더했다.
