BOJ - 12869 - 뮤탈 리스크
문제
문제
수빈이는 강호와 함께 스타크래프트 게임을 하고 있다. 수빈이는 뮤탈리스크 1개가 남아있고, 강호는 SCV N개가 남아있다.
각각의 SCV는 남아있는 체력이 주어져있으며, 뮤탈리스크를 공격할 수는 없다. 즉, 이 게임은 수빈이가 이겼다는 것이다.
뮤탈리스크가 공격을 할 때, 한 번에 세 개의 SCV를 공격할 수 있다.
- 첫 번째로 공격받는 SCV는 체력 9를 잃는다.
- 두 번째로 공격받는 SCV는 체력 3을 잃는다.
- 세 번째로 공격받는 SCV는 체력 1을 잃는다.
SCV의 체력이 0 또는 그 이하가 되어버리면, SCV는 그 즉시 파괴된다. 한 번의 공격에서 같은 SCV를 여러 번 공격할 수는 없다.
남아있는 SCV의 체력이 주어졌을 때, 모든 SCV를 파괴하기 위해 공격해야 하는 횟수의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 SCV의 수 N (1 ≤ N ≤ 3)이 주어진다. 둘째 줄에는 SCV N개의 체력이 주어진다. 체력은 60보다 작거나 같은 자연수이다.
출력
첫째 줄에 모든 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
#include <iostream>
#include <queue>
using namespace std;
// map
int n, m, num;
int map[64][64][64];
int visited[64][64][64];
//joy
int dz[] = {9, 9, 3, 3, 1, 1};
int dy[] = {3, 1, 1, 9, 9, 3};
int dx[] = {1, 3, 9, 1, 3, 9};
//unit
int unit[3];
void bfs(int sz, int sy, int sx)
{
queue<pair<pair<int, int>, int>> q;
q.push({{sz, sy}, sx});
visited[sz][sy][sx] = 1;
while(q.size())
{
int z = q.front().first.first;
int y = q.front().first.second;
int x = q.front().second;
q.pop();
if(visited[0][0][0])
break;
for(int i=0; i < 6; i++)
{ // 0이되면 죽은것이기 때문
int nz = max(0, z - dz[i]);
int ny = max(0, y - dy[i]);
int nx = max(0, x - dx[i]);
if(visited[nz][ny][nx])
continue;
visited[nz][ny][nx] = visited[z][y][x] + 1;
q.push({{nz, ny}, nx});
}
}
}
int main()
{
cin >> num;
for(int i=0; i < num; i++)
cin >> unit[i];
bfs(unit[0], unit[1], unit[2]);
cout << visited[0][0][0]-1 << endl;
return 0;
}
SOL
- 이런 dp문제는 이전의 dfs, bfs의 기본 문제인 map 형태의 변수의 개수를 생각해보면 된다.
- ex) x, y로 이루어진 map 의 변수의 개수는 2개
- 즉 위 문제의 변수의 개수는 scv의 개수인 3개 (x, y, z)인 것이다.
- ex) x, y로 이루어진 map 의 변수의 개수는 2개