이거도 나중에 써야지
|
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
|
using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;
using System.Threading.Channels;
namespace real연습
{
internal class Program
{
static void Main(string[] args)
{
int sugar = int.Parse(Console.ReadLine());
int[] k = { 3, 5 };
int[] dp = new int[sugar + 1];
for (int i = 1; i <= sugar; i++)
{
dp[i] = int.MaxValue;
}
for (int i = 0; i < 2; i++)
{
for (int j = k[i]; j <= sugar; j++)
{
if (dp[j - k[i]] != int.MaxValue)
dp[j] = Math.Min(dp[j], 1 + dp[j - k[i]]);
}
}
Console.WriteLine(dp[sugar] == int.MaxValue ? -1 : dp[sugar]);
}
}
}
|
cs |
bfs로도 풀린다.
그래프 탐색은 신이고 무적이다
|
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;
using System.Collections.Generic;
using System.Text;
using System.Linq;
using System.Threading.Channels;
namespace real연습
{
internal class Program
{
static void Main(string[] args)
{
int sugar = int.Parse(Console.ReadLine());
int[] k = { 3, 5 };
int[] graph = new int[sugar + 1];
Queue<int> q = new Queue<int>();
HashSet<int> visited = new HashSet<int>();
q.Enqueue(0);
visited.Add(0);
while (q.Count != 0)
{
int current = q.Dequeue();
for (int i = 0; i < 2; i++)
{
int delta = current + k[i];
if (visited.Contains(delta) == false)
{
if (delta >= 0 && delta <= sugar)
{
graph[delta] = 1 + graph[current];
q.Enqueue(delta);
visited.Add(delta);
}
}
}
if (graph[sugar] != 0)
{
break;
}
}
Console.WriteLine(graph[sugar] == 0 ? -1 : graph[sugar]);
}
}
}
|
cs |
'코끼리' 카테고리의 다른 글
| [백준] 2293 동전 1 [DP] (0) | 2024.09.12 |
|---|
