12869. 뮤탈리스크

[백준, 골드, c++]

어릴적 해봤던 스타크래프트 게임이다. 뮤탈리스크는 3개의 대상을 공격할 수 있다.
모든 SCV 를 파괴하기 위한 공격 횟수 최솟값을 출력해야하는데, SCV 가 최대 3대 라서 완탐
으로 해도 되지 않을 까 하는 생각을 했다. 2대 일때 적용 가능한 재귀 함수를 만들었고,
3대 적용 가능한 재귀 함수를 만들었다.

int play_pair(int life1, int life2)
int play_tuple(int life1, int life2, int life3)

결과는 시간초과였다. 하지만 완탐의 꽃은 캐쉬다.

int cache[61][61][61];

scv 의 최대 체력이 60이고 3대이기 때문에, 61,61,61 로 설정했다.
scv 의 순서와 관계없이 결과는 동일하기 때문에, play_tuple 의 파라미터를 정렬해서
cache 를 참조하면 되겠다.

각각의 scv 의 체력을 시작점 으로 두고, 0을 종점으로 둔 그래프를 탐색하는 것이다.
탐색 가능한 경로는 6가지가 되겠다.
특정 scv 의 체력을 a 라고 둘 때 예시를 들면 다음과 같이 할 수 있겠다.
int na = max(0, a - _a[i][0]);

전체 소스 코드 (opens in a new tab)

전체 로직 흐름

1. 6가지 밖에 안되니까 수작업하기

int _a[6][3] = {
	{9, 3, 1},
	{9, 1, 3},
	{3, 1, 9},
	{3, 9, 1},
	{1, 3, 9},
	{1, 9, 3}
};

2. SCV 의 개수에 따라 다른 로직 적용하기

if (N == 3) {
    memset(cache, -1, sizeof(cache));
    cout << play_tuple(life[0], life[1], life[2]);
    return 0;
}
 
if (N == 2) {
    cout << play_pair(life[0], life[1]);
    return 0;
}
 
// N == 1
cout << ((life[0] - 1) / attack) + 1;

정리

문제를 보고 bfs 가 적용가능한 로직이구나를 생각할 수 있게 하는 문제였던 것 같다.
여기서는 scv 가 3개 밖에 없는데, 20개 까지 나오는 문제가 있다... 다이아5...

나중에 도전해볼까...?

단순 bfs 로는 불가능 할 것 같고, 체력이 많은 scv 를 먼저 때리는 로직을 짜면 할 수 있지 않을까...?