12869번: 뮤탈리스크
1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다.
www.acmicpc.net
dp[hp1][hp2][hp3] : SCV의 체력이 각각 hp1, hp2, hp3 남았을 때 공격해야할 횟수의 최솟값
뮤탈리스크는 일반적으로 한 번 공격할 때 3기의 SCV를 공격할 수 있습니다.
스타크래프트에서는 9, 6, 3 순서대로 데미지가 들어가지만 이 문제에서는 9, 3, 1 순서대로 데미지가 들어갑니다.
(이거를 쿠션데미지라고 합니다.)
SCV의 체력이 0이하가 되면 파괴되고, 한 번의 공격에서 같은 SCV를 두 번이상 공격할 수 없습니다.
1번 SCV를 먼저 공격했을 때 쿠션데미지를 2번, 3번 순으로 넣을 때 / 3번, 2번 순으로 넣을 때를 각각 구해줍니다.
마찬가지로 2번, 3번 SCV를 먼저 공격했을 때도 쿠션데미지를 넣는 경우를 각각 구해줍니다.
정리하자면
1 -> 2 -> 3
1 -> 3 -> 2
2 -> 1 -> 3
2 -> 3 -> 1
3 -> 1 -> 2
3 -> 2 -> 1
위의 순서를 모두 구한 것의 최솟값을 출력해주시면 됩니다.
재귀를 돌리는 도중에 체력이 0이하가 되면 0으로 맞춰줘야합니다. (배열의 음수인덱스 참조 가능성)
|
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
|
#include <iostream>
#include <cstring>
#include <algorithm>
#define INF 2147483647
using namespace std;
int dp[61][61][61];
int list[3];
int N;
int sub(int x, int y) {
return x > y ? x - y : 0;
}
int func(int hp1, int hp2, int hp3) {
if (!hp1 && !hp2 && !hp3) return 0;
int &ret = dp[hp1][hp2][hp3];
if (ret != -1) return ret;
ret = INF;
if (hp1) {
ret = min(ret, func(sub(hp1, 9), sub(hp2, 3), sub(hp3, 1)) + 1);
ret = min(ret, func(sub(hp1, 9), sub(hp2, 1), sub(hp3, 3)) + 1);
}
if (hp2) {
ret = min(ret, func(sub(hp1, 3), sub(hp2, 9), sub(hp3, 1)) + 1);
ret = min(ret, func(sub(hp1, 1), sub(hp2, 9), sub(hp3, 3)) + 1);
}
if (hp3) {
ret = min(ret, func(sub(hp1, 3), sub(hp2, 1), sub(hp3, 9)) + 1);
ret = min(ret, func(sub(hp1, 1), sub(hp2, 3), sub(hp3, 9)) + 1);
}
return ret;
}
void input() {
cin >> N;
for (int i = 0; i < N; i++) {
cin >> list[i];
}
memset(dp, -1, sizeof(dp));
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
cout << func(list[0], list[1], list[2]) << '\n';
return 0;
}
|
cs |
'algorithm > dp' 카테고리의 다른 글
| boj 1563 개근상 (0) | 2021.06.02 |
|---|---|
| boj 10800 컬러볼 (0) | 2021.04.09 |
| boj 1520 내리막 길 (0) | 2021.03.28 |
| boj 1937 욕심쟁이 판다 (0) | 2021.03.28 |
| boj 2201 이친수 찾기 (2) | 2021.03.24 |