Algorithm/Baekjoon
[Algorithm]Baekjoon 12869번 : 뮤탈리스크
MaxLevel
2024. 3. 24. 23:00
https://www.acmicpc.net/problem/12869
12869번: 뮤탈리스크
1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다.
www.acmicpc.net
|
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
60
61
62
63
64
65
|
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
using namespace std;
int n;
int scvHPArr[3] = { 0 };
int dp[61][61][61] = { 0 };
int attacksInfo[6][3] = { {9,3,1}, {9,1,3}, {3,9,1}, {3,1,9}, {1,9,3}, {1,3,9} };
int dfs(int firstHP, int secondHP, int thirdHP)
{
if (firstHP <= 0 && secondHP <= 0 && thirdHP <= 0)
{
return 0;
}
firstHP = max(firstHP, 0);
secondHP = max(secondHP, 0);
thirdHP = max(thirdHP, 0);
if (dp[firstHP][secondHP][thirdHP] > 0) return dp[firstHP][secondHP][thirdHP];
dp[firstHP][secondHP][thirdHP] = 60;
for (int i = 0; i < 6; ++i)
{
dp[firstHP][secondHP][thirdHP] = min(dp[firstHP][secondHP][thirdHP], dfs(firstHP - attacksInfo[i][0], secondHP - attacksInfo[i][1], thirdHP - attacksInfo[i][2]) + 1);
}
return dp[firstHP][secondHP][thirdHP];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 0; i < n; ++i)
{
cin >> scvHPArr[i];
}
cout << dfs(scvHPArr[0], scvHPArr[1], scvHPArr[2]);
}
|
cs |
최소의 공격횟수로 최대 3개의 scv의 체력을 0으로 만들어야 하는 문제이다.
모든경우를 따지면서 재귀를 반복하면서 최소값을 기록해주면 되는데, 유의해야할 점은 체력을 깎다가보면 음수가 될 수 있다. 배열의 음수인덱스에 접근하면 터지기 때문에 음수일경우 0으로 조정해주는 코드를 작성해줘야 한다.
위 코드처럼 주어진 체력에서 깎아내려도 되고, 0부터시작해서 데미지를 누적하다가 scv체력들을 넘었을 때 끝내도 된다.
|
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
60
61
62
63
64
65
66
67
|
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
using namespace std;
int n;
int scvHPs[3] = { 0 };
int dp[71][71][71] = { 0 };
int attacksInfo[6][3] = { {9,3,1}, {9,1,3}, {3,9,1}, {3,1,9}, {1,9,3}, {1,3,9} };
int dfs(int firstHP, int secondHP, int thirdHP)
{
if (firstHP >= scvHPs[0] && secondHP >= scvHPs[1] && thirdHP >= scvHPs[2])
{
return 0;
}
firstHP = min(firstHP, scvHPs[0]);
secondHP = min(secondHP, scvHPs[1]);
thirdHP = min(thirdHP, scvHPs[2]);
if (dp[firstHP][secondHP][thirdHP] > 0) return dp[firstHP][secondHP][thirdHP];
dp[firstHP][secondHP][thirdHP] = 60;
for (int i = 0; i < 6; ++i)
{
int nextFirstHP = firstHP + attacksInfo[i][0];
int nextSecondHP = secondHP + attacksInfo[i][1];
int nextThirdHP = thirdHP + attacksInfo[i][2];
dp[firstHP][secondHP][thirdHP] = min(dp[firstHP][secondHP][thirdHP], dfs(nextFirstHP, nextSecondHP, nextThirdHP) + 1);
}
return dp[firstHP][secondHP][thirdHP];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 0; i < n; ++i)
{
cin >> scvHPs[i];
}
cout << dfs(0, 0, 0);
}
|
cs |